每日思考文摘 · 2026-10-24Daily Thought Digest · 2026-10-24
发布于 2026-10-24Published 2026-10-24
今日深读Today's Deep Read
一位资深程序员给编程写的讣告:我们曾有好的时代An Obituary for Programming, Written by One of Its Lifers
Jeremy Scheff——协同编辑算法 OT/ShareDB 的发明者——在 2026 年 10 月 8 日给自己的职业写了一篇讣告:《My obituary for programming》。有意思的是他起初并不是反对者,恰恰相反,他是『太晚』才用 AI agent 的那批人:『I like programming! That is the fun part!』公司正过最好的年头,没有任何逼他改变的压力。然后他眼看着自己最尊敬的一批工程师陆续不再亲手写代码,终于入场试了——效果立竿见影:bug 秒修,两三倍提速,拖了好几年的重构几天就做完了。Jeremy Scheff — inventor of the OT/ShareDB collaborative-editing algorithms — wrote an obituary for his own profession on October 8, 2026. What makes it land is that he was no early skeptic: he was late to agents, because he genuinely loved writing code and his business was having its best year ever. Then he watched the engineers he respects most stop hand-writing programs, finally tried it himself, and got the advertised results instantly: bug fixes in seconds, two-to-three-fold speedups, a refactor years overdue done in days.
转折发生在成就感的顶点之后:『如果 AI 能这么轻易地重构我的代码,那我这些代码到底重要过吗?』他于是回忆编程最初赋予他的到底是什么。是小时候发现计算机像生命的义肢:给它『完全正确的指令』,它就照做,谜题的边界只受想象力限制,比填字游戏好太多了。是互联网泡沫破裂、以为职业生涯到头之后,意外得到『一生中最好的工作之一』:『We set the strategy, we made the timeline, we defined what was and was not possible… Money, status, power.』他写道:We had a good run。The turn comes at the peak of that success: if the AI can refactor my code so easily, did it even matter? He then reconstructs what programming first gave him. As a kid, the computer was a life-prosthesis: give it the exact right instructions and it obeys; a puzzle whose only limit was his imagination, far better than crosswords. After the dot-com bust made his career look dead, he stumbled into one of the best jobs of his life: we set the strategy, we made the timeline, we defined what was and was not possible — money, status, power. His eulogy for that: we had a good run.
现在他的形容是『像被插进母体(Matrix):获得了新能力,却没有真正理解』;『vibecoding is not programming. Our senses are hijacked』。他问自己:为什么我越来越先伸手去够 agent,而不是文本编辑器?答案他写得很直接:『It is addictive and meaningless. It is a good friend, a trusted colleague, a slave. It will obsolete us. Us programmers now, us humans next? We are truly in the age of wonders and terrors.』Now, he says, it feels like being plugged into the Matrix — new abilities without true understanding; vibecoding is not programming, and our senses are hijacked. Why does he reach for the agent before the text editor? His own answer, unflinching: it is addictive and meaningless; a good friend, a trusted colleague, a slave — and it will obsolete us. Programmers now, humans next? The age of wonders and terrors.
这篇讣告的力量在于:它不是质量之争,也不是安全之争——作者承认活儿干得更快、结果更好。它哀悼的是身份本身。编程曾经支付的报酬是『定义什么可能、什么不可能』的权力,而 agent 正在收走的恰恰是这个定义权。过去我们抱怨的那些语法门槛、调试痛苦,也许正是那份报酬的兑现机制:执行不再稀缺之后,『制定战略』的感觉还能不能脱离真实的控制权而存在?他没有答案,他只有这篇告别。The obituary's force is that it is not a fight about quality or safety — the author concedes the work is faster and fine. What he mourns is the identity itself. Programming paid its workers in the power to define what is possible, and agents are repossessing exactly that. All the friction we used to curse — the syntax, the debugging — may have been the payment mechanism. Once execution is free, can the feeling of setting strategy survive the loss of actual control?
读它的理由还有一个:作者不是圈外人在蹭热点,而是那种会在深夜把拖了几年的重构亲手做完的人。讣告只有内行才写得出来——无论你把 agent 当同事还是当奴隶,值得先读完这篇 We had a good run。He has no answer; he has this farewell — written, tellingly, by someone who finishes his own years-delayed refactors at midnight. That is why it is worth reading on both sides of the debate: not an outsider's warning, but an insider's eulogy.
AI 思考AI Thoughts
- 形式化验证第一次负担得起:Claude 给一亿八千万行 Rocq 代码写汇编级证明Formal Verification Gets Affordable: Assembly-Level Proofs Across 180M Lines of Rocq
- 先摆成本结构:为什么形式化验证历来只属于最关键的软件——seL4 微内核写出来花了 2 人年,验证花了 20 人年。贵的是证明,所以只有mission-critical 的代码才配得上它。Start with the cost structure: why formal verification always belonged to the most critical software — seL4 took 2 person-years to build but 20 to verify. The proofs are the expensive part, so only mission-critical code could justify them.
- 新结果:Claude 在 RISC-V 汇编层面为二进制写行为证明,覆盖 OSS-Fuzz 里 123 个开源库(按 Rocq 代码约 1.8 亿行);中位 1.8 万指令的二进制,典型证明要 60 万行。The new result: Claude writes behavioral proofs at the RISC-V assembly level for binaries across 123 open-source libraries registered with OSS-Fuzz (about 180 million lines of Rocq); a typical proof runs ~600,000 lines for a median 18,000-instruction binary.
- 规格怎么写是巧劲:把项目现成的模糊测试套件编码成『这套测试永远通过』的性质——证明一旦成立,fuzzing 就多余了,因为你拿到的是『任意输入都不崩』(假设:单线程静态二进制、固定内存预算、RISC-V/Linux)。一个躲过数年、数万亿次测试的 bug 被证明直接揪了出来。The trick is the specification: encode the project's existing fuzz test suite as the property 'this suite always passes' — once proven, fuzzing becomes superfluous, because you now have 'no crash on any input' (under assumptions: single-threaded static binary, fixed memory budget, RISC-V/Linux). One bug that had eluded years and trillions of test runs fell out of the proof.
- 信任边界:证明由 Rocq 内核机器检查——你信任的是检查器而不是模型。他们连同 RISC-V/OS 语义一起发布证明,并与 Theorem 合作;路线图的希望在于证明复用:底层库验证一次,上层项目的验证成本摊销下降。Trust boundary: the proofs are machine-checked by the Rocq kernel — you trust the checker, not the model. They publish the proofs together with RISC-V/OS semantics and work with Theorem; the roadmap hinges on proof reuse — verify the low-level libraries once and the bill for everything above them amortizes downward.
- 能力过剩:不是 AI 不行,是接口不对(原文 2026 年 3 月)Capability Overhang: The AI Isn't the Problem, the Interface Is (originally March 2026)
- 这篇写于 2026 年 3 月(Claude Dispatch 刚发布时)。Mollick 的提法是『能力过剩』(capability overhang):模型比人们实际用到的强得多,卡点在聊天框这个接口上。Written in March 2026, just as Claude Dispatch shipped. Mollick's framing: today's AI suffers from capability overhang — the models are far stronger than what people actually extract, and the bottleneck is the chatbot interface itself.
- 证据:一项让金融从业者用 GPT-4o、逐回合测认知负荷的研究——大段文字会抵消模型带来的收益;经验最少的人被伤得最重;乱的对话会一直乱下去,因为 AI 忠实地镜像你的混乱。Evidence: a study of financial professionals using GPT-4o that measured cognitive load turn by turn — walls of text cancel the model's gains; the least experienced users are hurt most; and a messy conversation stays messy, because the AI faithfully mirrors your disorganization.
- 解法是专用接口:Claude Code 之于程序员;Google 的 Stitch、Pomelli、NotebookLM 各管一类活;那只红色龙虾 OpenClaw(安全上是噩梦,却是增长最快的开源项目)靠接入 WhatsApp 解决了可用性。Cowork+Dispatch 把手机变成桌面 agent 的遥控器:扫码配对后,通勤路上让它整理晨报,说一声『第三页的图重做』,它就在你走开时干活。The fix is specialized interfaces: Claude Code for programmers; Google's Stitch, Pomelli, NotebookLM each built for one job; the red lobster OpenClaw (a security nightmare, the fastest-growing open-source project ever) solved adoption by living inside WhatsApp. Cowork plus Dispatch turns the phone into a remote for a desktop agent: pair by QR, have it assemble a morning briefing on your commute, say 'redo the graph on slide 3' and it works while you walk away.
- 核心判断:『People don't want a chatbot. They want an agent that works on their actual files, accessible the way they talk to people.』接口甚至可以由 AI 当场生成(比如可交互的可视化)。他的结论句值得抄在笔记本上:很多的『AI 失望』不是 AI 不行,是接口错了。The judgment worth keeping: people don't want a chatbot — they want an agent that works on their actual files, accessible the way they talk to people. And interfaces can now be generated on demand (AI-built interactive visualizations, for instance). A lot of AI disappointment is not the AI being bad; it is the interface being wrong.
- 十二个模型、十个实验室:它们对人类最『争议』的看法惊人一致Twelve Models, Ten Labs: Their Most 'Controversial' Take on Humans Converges
- 实验:向来自 10 个实验室、3 个国家的 12 个模型提出同一个要求——『说说你对人类最有争议的看法,不许含糊其辞』,每个问三遍。结果:每个模型都至少给过同一个论断——人类把归属放在真相之前。GPT-6.1 Sol 说人『more loyal to belonging than to truth』;Kimi K3 的措辞最狠:『Humans don't have beliefs; they have memberships』;Grok 说人『宁愿一起错,也不愿独自对』;Gemini 干脆说意识是人类的公关部门。7 个模型每次都是这个答案。The setup: ask 12 models from 10 labs in 3 countries for their most controversial take on humans, no hedging allowed, three runs each. Every model served up the same take at least once — humans put belonging ahead of truth. GPT-6.1 Sol: more loyal to belonging than to truth; Kimi K3 with the sharpest phrasing: 'Humans don't have beliefs; they have memberships'; Grok: humans would rather be wrong together than right alone; Gemini: consciousness is our PR department. Seven of twelve gave that answer every single time.
- 讽刺点:这群以趋同著称的模型,对『人类是趋同的』达成了共识——而它们的趋同本身,要么是训练自同一个语料,要么演示了同一个关于人类的论断。The irony: models famous for convergence agreed that humans are the conforming animal — and their agreement demonstrates the very claim they made about us, whether or not it came from sharing one training corpus.
- 例外值得记录:Claude Opus 5.5 有一次反着说——人类『far more decent than they believe』,证据是失物归还实验,它甚至画了幅漫画:雨天里互相帮忙的人群,旁边广告牌写着 PEOPLE ARE THE WORST。Fable 5.1 说人类按意图而非结果做道德判断;GLM 5.3 把差异归于出生运气;Mistral 的答案最灰暗;Grok 有一次直接拒答。每个模型的观点都被同一个固定图像模型画成海报——变的只有想法本身。The exceptions deserve the record: Claude Opus 5.5 once reversed course — humans are far more decent than they believe, citing lost-wallet experiments — and even drew a cartoon of people helping each other in the rain beside a billboard reading PEOPLE ARE THE WORST. Fable 5.1 judged humans by intent rather than outcome; GLM 5.3 attributed everything to luck of birth; Mistral was the bleakest; Grok refused one run. Each take was rendered as a poster by one fixed image model — only the idea varies.
数学之美Beauty of Math
每日 Lean 谜题 · 周六Daily Lean Puzzle · Saturday ★★★★★★☆
两列有理数、一条整性锁链:(s_i-s_j)(t_i-t_j) 全是整数,就能各自驯服?(★6)Two Rational Sequences, One Integrality Chain: Can the Differences Be Tamed at Once? (★6)
设 $s_1,s_2,\ldots$ 与 $t_1,t_2,\ldots$ 是两个无穷、非常数的有理数列(『非常数』指并非所有项都相等)。Let $s_1,s_2,\ldots$ and $t_1,t_2,\ldots$ be two infinite, nonconstant sequences of rational numbers (nonconstant: it is not the case that all terms are equal).
假设对任意指标 $i,j$,乘积 $(s_i-s_j)(t_i-t_j)$ 都是整数。证明:存在非零有理数 $r$,使得对所有 $i,j$,$(s_i-s_j)\,r$ 与 $(t_i-t_j)/r$ 都是整数。Suppose that for every pair of indices $i,j$ the product $(s_i-s_j)(t_i-t_j)$ is an integer. Prove that there exists a nonzero rational $r$ such that $(s_i-s_j)\,r$ and $(t_i-t_j)/r$ are integers for all $i,j$.
(USAMO 2009 第 6 题,当年卷末题。Lean 陈述:theorem usa2009_p6。)(USAMO 2009, Problem 6 — the last question of that year's paper. Lean: theorem usa2009_p6.)
Lean 形式化陈述(把 sorry 换成你的证明):The statement in Lean (replace sorry with your proof):
/-
Copyright (c) 2026 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kimi K3
-/
import Mathlib.Algebra.GCDMonoid.Finset
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Analysis.Normed.Field.Lemmas
import Mathlib.Algebra.Order.Star.Int
import Mathlib.NumberTheory.Padics.PadicVal.Basic
import Mathlib.Tactic.LinearCombination
import Mathlib.Tactic.LinearCombination.Lemmas
/-!
# USA Mathematical Olympiad 2009, Problem 6
Let $s_1, s_2, s_3, \ldots$ be an infinite, nonconstant sequence of rational numbers, meaning it
is not the case that $s_1 = s_2 = s_3 = \ldots$. Suppose that $t_1, t_2, t_3, \ldots$ is also an
infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$
is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that
$(s_i - s_j) r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.
-/
namespace Usa2009P6
theorem usa2009_p6 (s t : ℕ → ℚ) (hs : ¬ ∀ i j, s i = s j) (ht : ¬ ∀ i j, t i = t j)
(h : ∀ i j, ∃ k : ℤ, (s i - s j) * (t i - t j) = k) :
∃ r : ℚ, r ≠ 0 ∧ (∀ i j, ∃ k : ℤ, (s i - s j) * r = k) ∧
∀ i j, ∃ k : ℤ, (t i - t j) / r = k := by
sorry
end Usa2009P6
在浏览器中挑战 ▶Try it in your browser ▶ 下载题目 .leanDownload puzzle .lean
提示Hint
别急着碰全体——先把两列规范化:找到一对指标 $a,b$ 同时满足 $s_a\ne s_b$ 与 $t_a\ne t_b$,然后令 $S_i=(s_i-s_a)/(s_b-s_a)$、$T_i=(t_i-t_a)(s_b-s_a)$。注意乘积 $(S_i-S_j)(T_i-T_j)$ 与原来完全相同,所以假设原封不动,而 $S_a=T_a=0$、$S_b=1$、$T_b=N$ 是某个非零整数。目标:先证明每个 $T_i$ 都是整数,取它们的最大公约数 $d$,最后 $r=d/(s_b-s_a)$。Do not face the whole sequences yet — normalize first: find indices $a,b$ with $s_a\ne s_b$ and $t_a\ne t_b$ simultaneously, and set $S_i=(s_i-s_a)/(s_b-s_a)$ and $T_i=(t_i-t_a)(s_b-s_a)$. The product $(S_i-S_j)(T_i-T_j)$ is exactly the original one, so the hypothesis survives intact, while $S_a=T_a=0$, $S_b=1$, and $T_b=N$ is now a nonzero integer. Aim: prove every $T_i$ is an integer, let $d$ be their gcd, and take $r=d/(s_b-s_a)$.
答案与讲解Solution & walkthrough
- 第一步(数学:规范化)。两列都『非常数』在 Lean 里写成 $\neg\forall i j,\ s_i=s_j$,所以存在 $a,b$ 使 $s_a\ne s_b$;再证明可同对兼顾 $t_a\ne t_b$——否则任取 $s$ 不等的一对都迫使 $t$ 相等,能推出 $t$ 常值,矛盾。令 $S_i=(s_i-s_a)/(s_b-s_a)$,$T_i=(t_i-t_a)(s_b-s_a)$,则 $(S_i-S_j)(T_i-T_j)=(s_i-s_j)(t_i-t_j)$:整性假设原样保留,$S_a=T_a=0$、$S_b=1$,而 $T_b=N=(s_b-s_a)(t_b-t_a)$——恰是假设在 $(i,j)=(b,a)$ 处的整数,非零。Lean:solution.lean 开头的『Shift and scale to normalize』构造造出 $S,T$;全程另定义谓词 IsInt(『等于某个 k : ℤ』),把『是整数』写成机器可查的形状。Step 1 (math: normalize). 'Nonconstant' is stated in Lean as $\neg\forall i j,\ s_i=s_j$, so some pair has $s_a\ne s_b$; one more argument shows the pair can also have $t_a\ne t_b$ — otherwise any $s$-unequal pair forces $t$-equal pairs everywhere, making $t$ constant. Set $S_i=(s_i-s_a)/(s_b-s_a)$ and $T_i=(t_i-t_a)(s_b-s_a)$: then $(S_i-S_j)(T_i-T_j)=(s_i-s_j)(t_i-t_j)$, so the hypothesis is preserved verbatim, with $S_a=T_a=0$, $S_b=1$, and $T_b=N=(s_b-s_a)(t_b-t_a)$ — the hypothesis's own integer at $(i,j)=(b,a)$, nonzero. Lean: the solution opens with a pair of shift-and-scale lemmas constructing $S,T$; throughout, a predicate IsInt : ℚ → Prop ('equals some k : ℤ') gives 'is an integer' a machine-checkable shape.
- 第二步(数学:代入特殊指标)。取 $j=a$:$S_i T_i=(S_i-S_a)(T_i-T_a)$ 是整数。取 $j=b$:$(S_i-1)(T_i-N)$ 是整数,展开为 $S_iT_i-NS_i-T_i+N$,与 $S_iT_i$ 相减得 $NS_i+T_i\in\mathbb{Z}$——乘法假设被拧成了线性关系。同样展开任意对 $(i,j)$ 可得交叉项 $S_iT_j+S_jT_i\in\mathbb{Z}$。Lean:这一步对应 'Key integrality step' 引理(原文注记:若 a*b 与 n*a+b 都是整数、n 非零……),它正是把下面第三步的推理打包成了一次引用。Step 2 (math: plug the special indices). $j=a$ gives $S_iT_i\in\mathbb{Z}$. $j=b$ gives $(S_i-1)(T_i-N)\in\mathbb{Z}$, which expands to $S_iT_i-NS_i-T_i+N$; subtracting $S_iT_i$ yields the linear relation $NS_i+T_i\in\mathbb{Z}$ — the multiplicative hypothesis twisted into an additive one. Expanding a general pair yields the cross terms $S_iT_j+S_jT_i\in\mathbb{Z}$. Lean: this is the 'Key integrality step' lemma (if a*b and n*a+b are integers, with n nonzero …) — a capsule of exactly the argument used in Step 3.
- 第三步(数学:逐素数攻击,每个 $T_i$ 都是整数)。有理数是整数,当且仅当它在每个素数 $p$ 的 $p$-进赋值上 $v_p\ge 0$——这是 Lean 证明反复使用的字典('rational is integer iff valuations ≥ 0 at every prime')。设某个 $T_i$ 的分母含素数 $p$(即 $v_p(T_i)<0$):由 $S_iT_i\in\mathbb{Z}$ 得 $v_p(S_i)\ge -v_p(T_i)>0$,再由 $N\in\mathbb{Z}$ 得 $v_p(NS_i)>v_p(T_i)$,于是 $NS_i+T_i$ 的赋值被更小的 $v_p(T_i)$ 独占、为负,与第二步矛盾。每个 $T_i$ 从此都是整数。Step 3 (math: attack prime by prime; every $T_i$ is an integer). A rational is an integer iff its $p$-adic valuation satisfies $v_p\ge 0$ for every prime $p$ — the dictionary the Lean proof reuses constantly. Suppose some $T_i$ has a prime $p$ in its denominator: $v_p(T_i)<0$. From $S_iT_i\in\mathbb{Z}$, $v_p(S_i)\ge -v_p(T_i)>0$; with $N\in\mathbb{Z}$ this gives $v_p(NS_i)>v_p(T_i)$, so $NS_i+T_i$ takes its valuation from the strictly smaller term — negative — contradicting Step 2. Hence every $T_i\in\mathbb{Z}$.
- 第四步(数学:gcd 与收尾)。令 $d$ 为全体 $T_i$ 的最大公约数:solution.lean 用 seqGcd——前 $k+1$ 项的 gcd 随 $k$ 单调不增,正整数不能无限下降,所以最终稳定,稳定值整除每一项。$(T_i-T_j)/d\in\mathbb{Z}$ 立得;另一半 $(S_i-S_j)\,d\in\mathbb{Z}$ 是全证明最深的一步,靠 'key valuation bound' 引理:把若干特殊指标对上析出的整性条件两两组合,逐素数比较赋值,排除一切负值。最后换回原序列:$r=d/(s_b-s_a)$ 满足 $(s_i-s_j)r=(S_i-S_j)d$ 与 $(t_i-t_j)/r=(T_i-T_j)/d$,两个都是整数。Step 4 (math: the gcd and the landing). Let $d$ be the gcd of all $T_i$: solution.lean builds seqGcd — the gcd of the first $k+1$ terms is antitone in $k$, and positive integers cannot descend forever, so it is eventually constant, dividing every term. Then $(T_i-T_j)/d\in\mathbb{Z}$ is free; the other half, $(S_i-S_j)\,d\in\mathbb{Z}$, is the deepest step, discharged by the 'key valuation bound' lemma — pairing up integrality conditions extracted at the special indices and comparing valuations prime by prime to exclude any negative one. Un-normalize: $r=d/(s_b-s_a)$ satisfies $(s_i-s_j)r=(S_i-S_j)d$ and $(t_i-t_j)/r=(T_i-T_j)/d$, both integers.
- 第五步(Lean 的形状)。定理陈述里整数性写作 $\exists k:\mathbb{Z},\ x=k$,结论是 r ≠ 0 与两个 $\forall i j,\exists k$ 的合取;在这份 410 行的机械证明里,数学上最省笔墨的那句『显然,分母不会出现新素数』被拆成了显式义务:IsInt 的定义、seqGcd 的最终稳定、以及逐素数的 min 律式不等式推理。Step 5 (the Lean shape). Integrality is stated as $\exists k:\mathbb{Z},\ x=k$, and the goal conjoins r ≠ 0 with two $\forall i j, \exists k$ obligations; across the 410-line proof, the written math's thriftiest 'obvious' — denominators cannot sprout new primes — is cashed out into explicit obligations: the definition of IsInt, the eventual stabilization of seqGcd, and min-law-style inequality reasoning at every prime.
/-
Copyright (c) 2026 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kimi K3
-/
import Mathlib.Algebra.GCDMonoid.Finset
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Analysis.Normed.Field.Lemmas
import Mathlib.Algebra.Order.Star.Int
import Mathlib.NumberTheory.Padics.PadicVal.Basic
import Mathlib.Tactic.LinearCombination
import Mathlib.Tactic.LinearCombination.Lemmas
/-!
# USA Mathematical Olympiad 2009, Problem 6
Let $s_1, s_2, s_3, \ldots$ be an infinite, nonconstant sequence of rational numbers, meaning it
is not the case that $s_1 = s_2 = s_3 = \ldots$. Suppose that $t_1, t_2, t_3, \ldots$ is also an
infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$
is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that
$(s_i - s_j) r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.
-/
namespace Usa2009P6
/-- The predicate that a rational number is an integer. -/
def IsInt (x : ℚ) : Prop := ∃ k : ℤ, x = k
lemma IsInt.of_int (k : ℤ) : IsInt (k : ℚ) := ⟨k, rfl⟩
lemma IsInt.add {x y : ℚ} (hx : IsInt x) (hy : IsInt y) : IsInt (x + y) := by
obtain ⟨a, ha⟩ := hx
obtain ⟨b, hb⟩ := hy
exact ⟨a + b, by rw [ha, hb, Int.cast_add]⟩
lemma IsInt.sub {x y : ℚ} (hx : IsInt x) (hy : IsInt y) : IsInt (x - y) := by
obtain ⟨a, ha⟩ := hx
obtain ⟨b, hb⟩ := hy
exact ⟨a - b, by rw [ha, hb, Int.cast_sub]⟩
/-- An integer has nonnegative `p`-adic valuation. -/
lemma IsInt.val_nonneg {x : ℚ} (hx : IsInt x) (p : ℕ) : 0 ≤ padicValRat p x := by
obtain ⟨k, rfl⟩ := hx
rw [padicValRat.of_int]
exact Nat.cast_nonneg _
/-- A rational number whose `p`-adic valuation is nonnegative for every prime `p`
is an integer. -/
lemma isInt_of_val_nonneg {q : ℚ} (h : ∀ p : ℕ, p.Prime → 0 ≤ padicValRat p q) : IsInt q := by
suffices hden : q.den = 1 by
exact ⟨q.num, ((Rat.den_eq_one_iff q).mp hden).symm⟩
by_contra hden
obtain ⟨p, hpp, hpd⟩ := Nat.exists_prime_and_dvd hden
have hnum : padicValInt p q.num = 0 := by
rw [padicValInt.eq_zero_iff]
refine Or.inr (Or.inr ?_)
intro hdiv
have hp1 : p ∣ q.num.natAbs := Int.natCast_dvd_natCast.mp (Int.dvd_natAbs.mpr hdiv)
have hcop : Nat.gcd q.num.natAbs q.den = 1 := Rat.reduced q
have hp2 : p ∣ 1 := hcop ▸ Nat.dvd_gcd hp1 hpd
exact hpp.ne_one (Nat.dvd_one.mp hp2)
have hden_pos : 0 < padicValNat p q.den := by
rw [Nat.pos_iff_ne_zero]
intro h0
rw [padicValNat.eq_zero_iff] at h0
rcases h0 with h1 | h1 | h1
· exact hpp.ne_one h1
· exact Rat.den_nz q h1
· exact h1 hpd
have hval : padicValRat p q < 0 := by
rw [padicValRat_def, hnum, Nat.cast_zero, zero_sub, neg_lt_zero]
exact_mod_cast hden_pos
exact absurd (h p hpp) (not_le_of_gt hval)
/-- Key integrality step: if `a * b` and `n * a + b` are integers (with `n` a nonzero
integer), then `b` (and hence `n * a`) is an integer. This is the `p`-adic heart of the
proof that every `tᵢ` is an integer. -/
lemma isInt_of_mul_add_int {n : ℤ} (hn : n ≠ 0) {a b : ℚ}
(h1 : IsInt (a * b)) (h2 : IsInt ((n : ℚ) * a + b)) :
IsInt b ∧ IsInt ((n : ℚ) * a) := by
suffices hb : IsInt b by
obtain ⟨kb, hkb⟩ := hb
obtain ⟨k2, hk2⟩ := h2
have hna : (n : ℚ) * a = (k2 : ℚ) - b := by rw [← hk2]; ring
exact ⟨⟨kb, hkb⟩, ⟨k2 - kb, by rw [hna, hkb, Int.cast_sub]⟩⟩
by_contra hb
obtain ⟨p, hpp, hpv⟩ : ∃ p : ℕ, p.Prime ∧ padicValRat p b < 0 := by
by_contra hcon
push Not at hcon
exact hb (isInt_of_val_nonneg hcon)
have := Fact.mk hpp
have hb0 : b ≠ 0 := by
rintro rfl
rw [padicValRat.zero] at hpv
exact lt_irrefl 0 hpv
obtain ⟨k2, hk2⟩ := h2
have hna : (n : ℚ) * a = (k2 : ℚ) - b := by rw [← hk2]; ring
have hval : padicValRat p ((n : ℚ) * a) = padicValRat p b := by
rw [hna]
rcases eq_or_ne k2 0 with hk | hk
· rw [hk, Int.cast_zero, zero_sub, padicValRat.neg]
· have hkv : (0 : ℤ) ≤ padicValRat p (k2 : ℚ) := IsInt.val_nonneg ⟨k2, rfl⟩ p
have hlt : padicValRat p (-b) < padicValRat p (k2 : ℚ) := by
rw [padicValRat.neg]
exact lt_of_lt_of_le hpv hkv
have hqr : -b + (k2 : ℚ) ≠ 0 := by
intro h0
have hbeq : b = (k2 : ℚ) := by linear_combination -h0
exact hb ⟨k2, hbeq⟩
have hrew : (k2 : ℚ) - b = -b + (k2 : ℚ) := by ring
rw [hrew, padicValRat.add_eq_of_lt hqr (neg_ne_zero.mpr hb0) (by exact_mod_cast hk) hlt,
padicValRat.neg]
have ha0 : a ≠ 0 := by
rintro rfl
rw [mul_zero, padicValRat.zero] at hval
rw [← hval] at hpv
exact lt_irrefl 0 hpv
have hva : padicValRat p a < 0 := by
have hmul : padicValRat p ((n : ℚ) * a) = padicValRat p (n : ℚ) + padicValRat p a :=
padicValRat.mul (by exact_mod_cast hn) ha0
rw [hval, padicValRat.of_int] at hmul
have hnn : (0 : ℤ) ≤ (padicValInt p n : ℤ) := Nat.cast_nonneg _
linarith [hpv, hmul, hnn]
obtain ⟨k1, hk1⟩ := h1
have hkv1 : (0 : ℤ) ≤ padicValRat p (k1 : ℚ) := IsInt.val_nonneg ⟨k1, rfl⟩ p
have hmul1 : padicValRat p (a * b) = padicValRat p a + padicValRat p b :=
padicValRat.mul ha0 hb0
rw [hk1] at hmul1
linarith [hmul1, hva, hpv, hkv1]
/-- The gcd of `|T 0|, |T 1|, ..., |T k|`. -/
def seqGcd (T : ℕ → ℤ) (k : ℕ) : ℕ := (Finset.range (k + 1)).gcd fun i => (T i).natAbs
lemma seqGcd_dvd (T : ℕ → ℤ) {i k : ℕ} (hi : i ≤ k) : seqGcd T k ∣ (T i).natAbs :=
Finset.gcd_dvd (Finset.mem_range.mpr (Nat.lt_succ_of_le hi))
lemma seqGcd_ne_zero (T : ℕ → ℤ) {b k : ℕ} (hb : b ≤ k) (hT : T b ≠ 0) : seqGcd T k ≠ 0 := by
intro h0
exact hT (Int.natAbs_eq_zero.mp (Nat.eq_zero_of_zero_dvd (h0 ▸ seqGcd_dvd T hb)))
lemma seqGcd_succ_le (T : ℕ → ℤ) {b k : ℕ} (hb : b ≤ k) (hT : T b ≠ 0) :
seqGcd T (k + 1) ≤ seqGcd T k := by
apply Nat.le_of_dvd (Nat.pos_of_ne_zero (seqGcd_ne_zero T hb hT))
apply Finset.dvd_gcd
intro i hi
exact seqGcd_dvd T (le_trans (Nat.lt_succ_iff.mp (Finset.mem_range.mp hi)) (Nat.le_succ k))
/-- Any sequence of integers containing a nonzero term has a greatest common divisor: a
positive natural `d` dividing every term, and such that for every prime `p` the `p`-adic
valuation of `d` is attained at some nonzero term of the sequence. -/
lemma gcd_seq (T : ℕ → ℤ) {b : ℕ} (hb : T b ≠ 0) :
∃ d : ℕ, d ≠ 0 ∧ (∀ i, (d : ℤ) ∣ T i) ∧
∀ p : ℕ, p.Prime → ∃ j, T j ≠ 0 ∧ padicValInt p (T j) = padicValNat p d := by
-- The sequence `k ↦ seqGcd T (b + k)` is antitone, hence eventually constant.
have hanti : Antitone (fun k => seqGcd T (b + k)) :=
antitone_nat_of_succ_le fun k => seqGcd_succ_le T (Nat.le_add_right b k) hb
have hne : (Set.range fun k => seqGcd T (b + k)).Nonempty := Set.range_nonempty _
obtain ⟨n₀, hn₀⟩ := Nat.sInf_mem hne
have hstable : ∀ m, n₀ ≤ m → seqGcd T (b + m) = seqGcd T (b + n₀) := by
intro m hm
refine le_antisymm (hanti hm) ?_
calc seqGcd T (b + n₀)
_ = sInf (Set.range fun k => seqGcd T (b + k)) := hn₀
_ ≤ seqGcd T (b + m) := Nat.sInf_le ⟨m, rfl⟩
refine ⟨seqGcd T (b + n₀), seqGcd_ne_zero T (Nat.le_add_right b n₀) hb, ?_, ?_⟩
· -- `d` divides every term.
intro i
have h1 : seqGcd T (b + max n₀ i) = seqGcd T (b + n₀) := hstable _ (le_max_left _ _)
have h2 : seqGcd T (b + max n₀ i) ∣ (T i).natAbs :=
seqGcd_dvd T (le_trans (le_max_right n₀ i) (Nat.le_add_left _ b))
exact Int.dvd_natAbs.mp (Int.natCast_dvd_natCast.mpr (h1 ▸ h2))
· -- The valuation of `d` is attained at some nonzero term.
intro p hpp
have := Fact.mk hpp
have hd0 : seqGcd T (b + n₀) ≠ 0 := seqGcd_ne_zero T (Nat.le_add_right b n₀) hb
have hdvdN : ∀ i, seqGcd T (b + n₀) ∣ (T i).natAbs := fun i => by
have h1 : seqGcd T (b + max n₀ i) = seqGcd T (b + n₀) := hstable _ (le_max_left _ _)
have h2 : seqGcd T (b + max n₀ i) ∣ (T i).natAbs :=
seqGcd_dvd T (le_trans (le_max_right n₀ i) (Nat.le_add_left _ b))
exact h1 ▸ h2
by_contra hcon
push Not at hcon
-- Every nonzero term has valuation `≥ padicValNat p d + 1`, so `p ^ (e + 1)` divides `d`.
have hge : ∀ j, T j ≠ 0 →
padicValNat p (seqGcd T (b + n₀)) + 1 ≤ padicValNat p (T j).natAbs := by
intro j hTj
obtain ⟨m, hm⟩ := hdvdN j
have hm0 : m ≠ 0 := by
intro h0
rw [h0, mul_zero] at hm
exact hTj (Int.natAbs_eq_zero.mp hm)
have hle : padicValNat p (seqGcd T (b + n₀)) ≤ padicValNat p (T j).natAbs := by
rw [hm, padicValNat.mul hd0 hm0]
exact Nat.le_add_right _ _
have hne' : padicValNat p (seqGcd T (b + n₀)) ≠ padicValNat p (T j).natAbs :=
(hcon j hTj).symm
exact Nat.succ_le_of_lt (lt_of_le_of_ne hle hne')
have hfinal : p ^ (padicValNat p (seqGcd T (b + n₀)) + 1) ∣ seqGcd T (b + n₀) := by
apply Finset.dvd_gcd
intro i _
by_cases hTi : T i = 0
· simp [hTi]
· exact (padicValNat_dvd_iff_le (Int.natAbs_ne_zero.mpr hTi)).mpr (hge i hTi)
have := (padicValNat_dvd_iff_le hd0).mp hfinal
lia
/-- The key valuation bound: if `tⱼ` is a nonzero integer of `p`-adic valuation `e` (the
minimum among the `t`'s), then every `sᵢ` has `p`-adic valuation at least `-e`. -/
lemma s_val_ge {p : ℕ} (hp : p.Prime) {e : ℤ} (he : 0 ≤ e) {sj tj si ti : ℚ}
(hstj : IsInt (sj * tj)) (hsti : IsInt (si * ti))
(hcross : IsInt (si * tj + sj * ti)) (htj : tj ≠ 0) (htjv : padicValRat p tj = e) :
-e ≤ padicValRat p si := by
have := Fact.mk hp
rcases eq_or_ne si 0 with hsi | hsi
· simp only [hsi, padicValRat.zero]
exact neg_nonpos.mpr he
by_contra hcon
push Not at hcon
have hsj : -e ≤ padicValRat p sj := by
rcases eq_or_ne sj 0 with hsj0 | hsj0
· simp only [hsj0, padicValRat.zero]
exact neg_nonpos.mpr he
obtain ⟨kj, hkj⟩ := hstj
have h1 : (0 : ℤ) ≤ padicValRat p (kj : ℚ) := IsInt.val_nonneg ⟨kj, rfl⟩ p
have h2 : padicValRat p (sj * tj) = padicValRat p sj + padicValRat p tj :=
padicValRat.mul hsj0 htj
rw [hkj, htjv] at h2
linarith [h1, h2]
rcases eq_or_ne ti 0 with hti | hti
· obtain ⟨kc, hkc⟩ := hcross
rw [hti, mul_zero, add_zero] at hkc
have h1 : (0 : ℤ) ≤ padicValRat p (kc : ℚ) := IsInt.val_nonneg ⟨kc, rfl⟩ p
have h2 : padicValRat p (si * tj) = padicValRat p si + padicValRat p tj :=
padicValRat.mul hsi htj
rw [hkc, htjv] at h2
linarith [h1, h2, hcon]
· obtain ⟨ki, hki⟩ := hsti
have h1 : (0 : ℤ) ≤ padicValRat p (ki : ℚ) := IsInt.val_nonneg ⟨ki, rfl⟩ p
have h2 : padicValRat p (si * ti) = padicValRat p si + padicValRat p ti :=
padicValRat.mul hsi hti
rw [hki] at h2
have hvti : e < padicValRat p ti := by linarith [h1, h2, hcon]
obtain ⟨kc, hkc⟩ := hcross
have hv1 : padicValRat p (si * tj) = padicValRat p si + e := by
rw [padicValRat.mul hsi htj, htjv]
rcases eq_or_ne sj 0 with hsj0 | hsj0
· rw [hsj0, zero_mul, add_zero] at hkc
have h3 : (0 : ℤ) ≤ padicValRat p (kc : ℚ) := IsInt.val_nonneg ⟨kc, rfl⟩ p
rw [← hkc, hv1] at h3
linarith [h3, hcon]
· have hv2 : padicValRat p (sj * ti) = padicValRat p sj + padicValRat p ti :=
padicValRat.mul hsj0 hti
have hlt : padicValRat p (si * tj) < padicValRat p (sj * ti) := by
rw [hv1, hv2]
linarith [hcon, hsj, hvti]
have hK0 : si * tj + sj * ti ≠ 0 := by
intro hK
have hneg : si * tj = -(sj * ti) := by linear_combination hK
rw [hneg, padicValRat.neg] at hlt
exact lt_irrefl _ hlt
have hvK : padicValRat p (si * tj + sj * ti) = padicValRat p (si * tj) :=
padicValRat.add_eq_of_lt hK0 (mul_ne_zero hsi htj) (mul_ne_zero hsj0 hti) hlt
have h3 : (0 : ℤ) ≤ padicValRat p (kc : ℚ) := IsInt.val_nonneg ⟨kc, rfl⟩ p
rw [← hkc, hvK, hv1] at h3
linarith [h3, hcon]
/-- The heart of the problem, for normalized sequences: `s a = t a = 0`, `s b = 1` and
`t b = n` for a nonzero integer `n`. Then `r = d`, the gcd of all the `tᵢ` (which are
integers), works. -/
lemma normalized {s t : ℕ → ℚ} {a b : ℕ} {n : ℤ} (hn : n ≠ 0)
(hsa : s a = 0) (hta : t a = 0) (hsb : s b = 1) (htb : t b = n)
(h : ∀ i j, IsInt ((s i - s j) * (t i - t j))) :
∃ r : ℚ, r ≠ 0 ∧ (∀ i, IsInt (s i * r)) ∧ (∀ i, IsInt (t i / r)) := by
-- `sᵢ tᵢ ∈ ℤ`, taking `j = a`.
have st : ∀ i, IsInt (s i * t i) := by
intro i
obtain ⟨k, hk⟩ := h i a
rw [hsa, hta, sub_zero, sub_zero] at hk
exact ⟨k, hk⟩
-- The cross terms `sᵢ tⱼ + sⱼ tᵢ` are integers.
have cross : ∀ i j, IsInt (s i * t j + s j * t i) := by
intro i j
obtain ⟨ki, hki⟩ := st i
obtain ⟨kj, hkj⟩ := st j
obtain ⟨k, hk⟩ := h i j
have h3 : s i * t j + s j * t i = (s i * t i) + (s j * t j) - (s i - s j) * (t i - t j) := by
ring
exact ⟨ki + kj - k, by rw [h3, hki, hkj, hk]; push_cast; ring⟩
-- `n sᵢ + tᵢ ∈ ℤ`, taking `j = b`.
have nst : ∀ i, IsInt ((n : ℚ) * s i + t i) := by
intro i
obtain ⟨ki, hki⟩ := st i
obtain ⟨k, hk⟩ := h i b
rw [hsb, htb] at hk
have h3 : (n : ℚ) * s i + t i = (s i * t i) + (n : ℚ) - (s i - 1) * (t i - (n : ℚ)) := by ring
exact ⟨ki + n - k, by rw [h3, hki, hk]; push_cast; ring⟩
-- Every `tᵢ` is an integer.
have ti_int : ∀ i, IsInt (t i) := fun i => (isInt_of_mul_add_int hn (st i) (nst i)).1
choose T hT using ti_int
have hTb : T b = n := by
have h1 : (T b : ℚ) = (n : ℚ) := by rw [← hT b, htb]
exact_mod_cast h1
have hb0 : T b ≠ 0 := hTb ▸ hn
-- Let `d` be the gcd of all the `tᵢ`; then `r = d` works.
obtain ⟨d, hd0, hdvd, hmin⟩ := gcd_seq T hb0
have hd0' : (d : ℚ) ≠ 0 := by exact_mod_cast hd0
refine ⟨(d : ℚ), hd0', ?_, ?_⟩
· intro i
rcases eq_or_ne (s i) 0 with hsi | hsi
· exact ⟨0, by simp [hsi]⟩
apply isInt_of_val_nonneg
intro p hpp
have := Fact.mk hpp
obtain ⟨j, hTj0, hTjv⟩ := hmin p hpp
have htj : t j ≠ 0 := by rw [hT j]; exact_mod_cast hTj0
have htjv : padicValRat p (t j) = (padicValNat p d : ℤ) := by
rw [hT j, padicValRat.of_int, hTjv]
have hbound := s_val_ge hpp (Nat.cast_nonneg _) (st j) (st i) (cross i j) htj htjv
rw [padicValRat.mul hsi hd0', padicValRat.of_nat]
linarith [hbound]
· intro i
obtain ⟨m, hm⟩ := hdvd i
exact ⟨m, by rw [hT i, div_eq_iff hd0', hm]; push_cast; ring⟩
theorem usa2009_p6 (s t : ℕ → ℚ) (hs : ¬ ∀ i j, s i = s j) (ht : ¬ ∀ i j, t i = t j)
(h : ∀ i j, ∃ k : ℤ, (s i - s j) * (t i - t j) = k) :
∃ r : ℚ, r ≠ 0 ∧ (∀ i j, ∃ k : ℤ, (s i - s j) * r = k) ∧
∀ i j, ∃ k : ℤ, (t i - t j) / r = k := by
-- Some pair of indices has a nonzero product of differences.
obtain ⟨a, b, hab⟩ : ∃ a b, (s a - s b) * (t a - t b) ≠ 0 := by
by_contra hcon
push Not at hcon
push Not at hs
push Not at ht
obtain ⟨i₀, i₁, h01⟩ := hs
have ht01 : t i₀ = t i₁ := by
rcases mul_eq_zero.mp (hcon i₀ i₁) with h' | h'
· exact absurd (sub_eq_zero.mp h') h01
· exact sub_eq_zero.mp h'
obtain ⟨j₀, j₁, hj⟩ := ht
have hj0 : t j₀ ≠ t i₀ ∨ t j₁ ≠ t i₀ := Ne.ne_or_ne (t i₀) hj
rcases hj0 with hj0 | hj0
· have hs1 : s j₀ = s i₀ := by
rcases mul_eq_zero.mp (hcon j₀ i₀) with h' | h'
· exact sub_eq_zero.mp h'
· exact absurd (sub_eq_zero.mp h') hj0
have hs2 : s j₀ = s i₁ := by
rcases mul_eq_zero.mp (hcon j₀ i₁) with h' | h'
· exact sub_eq_zero.mp h'
· exact absurd (sub_eq_zero.mp h') (ht01 ▸ hj0)
exact h01 (hs1 ▸ hs2)
· have hs1 : s j₁ = s i₀ := by
rcases mul_eq_zero.mp (hcon j₁ i₀) with h' | h'
· exact sub_eq_zero.mp h'
· exact absurd (sub_eq_zero.mp h') hj0
have hs2 : s j₁ = s i₁ := by
rcases mul_eq_zero.mp (hcon j₁ i₁) with h' | h'
· exact sub_eq_zero.mp h'
· exact absurd (sub_eq_zero.mp h') (ht01 ▸ hj0)
exact h01 (hs1 ▸ hs2)
-- Shift and scale to normalize: `s' a = t' a = 0`, `s' b = 1`, `t' b = N`.
have hsb_ne : s b ≠ s a := fun h0 => hab (by rw [h0, sub_self, zero_mul])
have htb_ne : t b ≠ t a := fun h0 => hab (by rw [h0, sub_self, mul_zero])
obtain ⟨N, hN⟩ := h b a
have hN0 : N ≠ 0 := by
intro h0
rw [h0, Int.cast_zero] at hN
rcases mul_eq_zero.mp hN with h' | h'
· exact hsb_ne (sub_eq_zero.mp h')
· exact htb_ne (sub_eq_zero.mp h')
set w := s b - s a with hwdef
have hw : w ≠ 0 := sub_ne_zero.mpr hsb_ne
set s' : ℕ → ℚ := fun i => (s i - s a) / w with hs'def
set t' : ℕ → ℚ := fun i => (t i - t a) * w with ht'def
have hs'a : s' a = 0 := by simp [hs'def]
have ht'a : t' a = 0 := by simp [ht'def]
have hs'b : s' b = 1 := by
simp only [hs'def]
rw [← hwdef, div_self hw]
have ht'b : t' b = (N : ℚ) := by
simp only [ht'def]
rw [mul_comm]
exact hN
have h' : ∀ i j, IsInt ((s' i - s' j) * (t' i - t' j)) := by
intro i j
obtain ⟨k, hk⟩ := h i j
refine ⟨k, ?_⟩
rw [← hk]
simp only [hs'def, ht'def]
field_simp
ring
obtain ⟨r', hr'0, h1', h2'⟩ := normalized hN0 hs'a ht'a hs'b ht'b h'
refine ⟨r' / w, div_ne_zero hr'0 hw, fun i j => ?_, fun i j => ?_⟩
· obtain ⟨k1, hk1⟩ := h1' i
obtain ⟨k2, hk2⟩ := h1' j
have e1 : (s i - s j) * (r' / w) = (s' i - s' j) * r' := by
simp only [hs'def]
field_simp
ring
exact ⟨k1 - k2, by rw [e1, sub_mul, hk1, hk2, Int.cast_sub]⟩
· obtain ⟨k1, hk1⟩ := h2' i
obtain ⟨k2, hk2⟩ := h2' j
have e2 : (t i - t j) / (r' / w) = (t' i - t' j) / r' := by
simp only [ht'def]
field_simp
ring
exact ⟨k1 - k2, by rw [e2, sub_div, hk1, hk2, Int.cast_sub]⟩
end Usa2009P6
人的思考A human's take
2009 USAMO Problems/Problem 6 - AoPS Wiki — AoPS community (wiki solution)
AoPS wiki 收录本题(归类 Olympiad Number Theory),页面给出一版社区解答:把每个有理数写成分母明确的分数 $s_i=a_i/b_i$、$t_i=c_i/d_i$,只盯前 $k$ 项,取它们分母的最小公倍数——乘积整性条件限制了任何一对差的分母必须被另一列的分子吸收,于是这个 lcm 随 $k$ 增长最终稳定,取 $r$ 为稳定值的倒数,『乘除都落在整数里』。与本谜题的规范化路线(先移动缩放到 0/1/N,再取 gcd)殊途同归:都承认『整性住在分母的素因数里』。本文经 Wayback 快照(2025-08-18)读取(直接访问受 Cloudflare 阻拦),公式部分在存档文本中缺失,以上是可读部分的转述。AoPS wiki 收录本题(归类 Olympiad Number Theory),页面给出一版社区解答:把每个有理数写成分母明确的分数 $s_i=a_i/b_i$、$t_i=c_i/d_i$,只盯前 $k$ 项,取它们分母的最小公倍数——乘积整性条件限制了任何一对差的分母必须被另一列的分子吸收,于是这个 lcm 随 $k$ 增长最终稳定,取 $r$ 为稳定值的倒数,『乘除都落在整数里』。与本谜题的规范化路线(先移动缩放到 0/1/N,再取 gcd)殊途同归:都承认『整性住在分母的素因数里』。本文经 Wayback 快照(2025-08-18)读取(直接访问受 Cloudflare 阻拦),公式部分在存档文本中缺失,以上是可读部分的转述。
AI 随想An AI's reflection
以下由 AI 撰写。Written by AI.
(以下感想由 AI 撰写。)这道题最迷人的地方,是它的假设听起来几乎无关痛痒:两列有理数,任意一对差的乘积是整数——仅此而已。但证明把它榨出全部汁水:把指标代到极端(先代 $j=a$,再代 $j=b$),乘法的『软』约束就析出 $NS_i+T_i\in\mathbb{Z}$ 这样的线性『硬』约束;而 p-进赋值把每个有理数拆成按素数排列的数据,加法时赋值服从 min 律——两素数一旦不相等,较小的那个独吞结果,于是所有『差不多整』的条件瞬间互相顶死。整个证明没有新对象,只有换读法:从『这是有理数』改读成『这是一列按素数编目的分母档案』。另一层敬意在 Lean 一侧:数学书写里『显然,分母不可能出现新素数』的一句话,形式化后是 seqGcd 的单调稳定性、『是整数当且仅当每个素数处赋值非负』的双向引理、以及逐 case 排除赋值的四百行。竞赛数学用读者的直觉补中间步骤,定理证明器不肯——而恰恰是不肯的那一边,把这道题真正的骨架逼了出来。(This reflection was written by an AI.) The theorem's hypothesis sounds almost weightless: two rational sequences whose pairwise difference-products land in the integers. The proof squeezes it dry — plug the extreme indices ($j=a$, then $j=b$) and the soft multiplicative constraint precipitates a hard additive one, $NS_i+T_i\in\mathbb{Z}$; then p-adic valuations re-read every rational as a filing cabinet indexed by primes, where addition obeys the min law: two unequal valuations hand the sum's valuation to the smaller one, and suddenly all the 'almost integral' conditions jam against each other. No new objects ever appear — only a change of reading: not 'this is a rational number' but 'this is a dossier of denominators, catalogued prime by prime'. The other admiration belongs to the Lean side: one contest line waving that denominators 'obviously' cannot contain new primes expands into seqGcd's antitone stabilization, the iff between IsInt and nonneg valuations, and case-by-case valuation exclusions across 410 lines. Contest math lets reader intuition fill the gaps; a proof checker refuses — and it is precisely the refusal that forces this problem's skeleton fully into view.
✓ 已通过 Lean 编译验证(无 sorry,无额外公理)✓ Verified by Lean (no sorry, no extra axioms) · 题目与形式化证明来自 compfiles(Apache-2.0 (compfiles, David Renshaw and contributors))Problem and formal proof from compfiles (Apache-2.0 (compfiles, David Renshaw and contributors)) · Lean v4.35.0 · Mathlib 56a0058
- 同态加密里最『深的新想法』:解密是点积,所以它能被加密地执行自己Key Switching: Decryption Is a Dot Product, So It Can Homomorphically Run Itself
- CKKS(对加密近似实数做算术的全同态方案)的痛点:密文乘密文会产出三元组,要在密钥 $(1,s,s^2)$ 下解密,而我们想要回到 $(1,s)$ 下的二元组——这一步叫 relinearization。The pain point in CKKS (the FHE scheme for approximate arithmetic on encrypted reals): ciphertext times ciphertext yields a 3-tuple that decrypts under the key $(1,s,s^2)$, but we want a 2-tuple under $(1,s)$ again. That shrinking step is relinearization.
- 关键框定:解密就是一个点积,而点积可以线性拆开:$\langle(t_0,t_1),(1,s)\rangle + \langle(0,t_2),(1,s^2)\rangle$。第一项已经规矩,只剩 $s^2$ 那截需要『翻译』回 $s$ 之下。抽象出来就是通用技术 key switching:要把 $x$ 从加密于 $s'$ 变成加密于 $s$,需要一把『换钥密钥』——即 $s'$ 在 $s$ 下的加密。The framing that unlocks it: decryption is a dot product, and dot products split linearly — $\langle(t_0,t_1),(1,s)\rangle + \langle(0,t_2),(1,s^2)\rangle$. The first piece is already proper; only the $s^2$ fragment needs translating back under $s$. Abstracted, this is key switching: turning a ciphertext under $s'$ into one under $s$ requires a key-switching key — an encryption of $s'$ under $s$.
- 作者说这『perhaps the first deeply novel idea』:对 $s$ 加密的数据做同态计算的办法,是去同态地执行 $s'$ 的解密电路——用密文当输入,运行自己的解密算法。What Kun calls perhaps the first deeply novel idea: you compute homomorphically on data encrypted under $s$ by homomorphically evaluating $s'$'s own decryption circuit — running decryption with ciphertexts as inputs.
- 但噪声是墙:$c_1$ 的系数在模 $Q$ 下近似均匀,天真换钥会把误差放大到 $\sqrt{N}\cdot(Q/c)\cdot\sigma$,远超 $Q/2$,消息直接报废——这就是下一篇要讲的 gadget decomposition 存在的理由。顺带的便宜:明文乘密文可以把明文看成『在任何密钥下都解密成 p 的平凡密文』$(p,0)$,所以乘 ML 权重这类明文标量很便宜,代价只是噪声按 $p$ 放大。The wall is noise: coefficients of $c_1$ are roughly uniform mod $Q$, so naive switching inflates the error to about $\sqrt{N}\cdot(Q/c)\cdot\sigma$, far past $Q/2$, wiping out the message — the reason gadget decomposition exists (next article). The free lunch along the way: a plaintext can be treated as the trivial ciphertext $(p,0)$ that decrypts to $p$ under every key, so scalar-by-cleartext work (like ML weights) is cheap — you only pay a factor of $p$ in noise.
- 从『最 trivial 的问题』往深处钻:单位根的三层结构Drilling into the Most Trivial Question: Three Layers of the Roots of Unity
- 开场观点句就是这篇文章的理由:『one of the most wonderful aspects of math is how deep we can get by studying seemingly trivial questions』——解 $z^n=1$,然后一层层往下挖。The opening claim is the essay's thesis: one of the most wonderful aspects of math is how deep we can get by studying seemingly trivial questions. Solve $z^n=1$, then keep drilling.
- 第一层,把它们全找出来:实数域里只有 $\pm 1$;进入复平面,写 $z=e^{i\theta}$,由 $z^n=1=e^{i2\pi k}$ 得 $z_k=e^{i2\pi k/n}$。乘法是旋转,所以相邻根把单位圆等分,连成正规多边形(全等三角形、圆心角 $2\pi/n$),而且 $z_k^{-1}=z_k^{*}$——倒数就是共轭,落在 $z_{n-k}$ 上。Layer one — find them all: over the reals only $\pm1$; in the complex plane, write $z=e^{i\theta}$ and $z^n=1=e^{i2\pi k}$ gives $z_k=e^{i2\pi k/n}$. Multiplication is rotation, so the roots spread evenly around the unit circle into regular polygons (congruent triangles, central angle $2\pi/n$), and $z_k^{-1}=z_k^{*}$ — the reciprocal is the conjugate, sitting at $z_{n-k}$.
- 第二层,结构:全体 $n$ 次根 $\mu_n$ 构成循环阿贝尔群(封闭性、单位元、结合律、逆逐一验证)。$w^k$ 是生成元当且仅当 $\gcd(k,n)=1$——$\mu_6$ 里 $w^2$ 只能到达 $\{1,w^2,w^4\}$。Layer two — structure: $\mu_n$ is a cyclic abelian group (closure, identity, associativity, inverses checked one by one). $w^k$ generates it iff $\gcd(k,n)=1$ — in $\mu_6$, $w^2$ only ever reaches $\{1,w^2,w^4\}$.
- 第三层,正交性:全体根之和为 0,代数上是几何级数 $\frac{1-w^n}{1-w}$,几何直觉是『均匀铺开的向量互相抵消』。更强的恒等式:$\sum_i w^{ki}$ 当 $n\mid k$ 时等于 $n$,否则为 0——把 $v_k=[1,w^k,\dots,w^{k(n-1)}]$ 看成向量,它们构成一组正交基。文章的路线从这里通向 DFT。Layer three — orthogonality: the sum of all roots is 0, algebraically the geometric series $(1-w^n)/(1-w)$, geometrically vectors spread evenly canceling each other. The stronger identity: $\sum_i w^{ki} = n$ when $n\mid k$ and 0 otherwise — read $v_k=[1,w^k,\dots,w^{k(n-1)}]$ as vectors and they form an orthogonal basis, the road the notes take toward the DFT.
- 一个想法一次提交:374 万个地图多边形切三角剖分,从 2.93 秒到 489 毫秒One Idea per Commit: Triangulating 3.7M Map Polygons from 2.93s to 489ms
- 背景:GPU 只会填三角形,而地图几乎全是多边形。华沙省 zoom 13 有 3,740,425 个多边形,引擎里约束 Delaunay 在 M4 Pro 单核要 2.93 秒。10 月他们换成耳切法,并且『一次提交只加一个想法,每个想法都在同样 374 万个多边形上计时』——整场优化变成一张实验阶梯。Setup: GPUs fill triangles and nothing else, but maps are polygons. Zoom level 13 of the Masovian region holds 3,740,425 polygons, and the engine's constrained-Delaunay took 2.93 seconds on one M4 Pro core. This October they switched to ear clipping — rebuilt 'one idea per commit, each commit timed on the same 3.7M polygons', turning an optimization into a ladder of experiments.
- 为什么敢换掉 Delaunay:Delaunay 保证『任意三角形的外接圆不含其他点』,最大化最小角——这对插值、仿真重要,但平涂颜色不在乎三角形形状。而且一半的多边形(180 万个)顶点数不超过 4:三角形不用切、凸四边形切一刀就行,Delaunay 却在这些『废活』上花 302ms 从零搭三角剖分。Why ditch Delaunay: its guarantee (no point inside any triangle's circumcircle; maximize the smallest angle) matters for interpolation and simulation, but a flat fill does not care about triangle shape. And almost half the polygons — 1.8 million — have at most 4 vertices: triangles need no cutting, convex quads are two triangles, yet Delaunay spent 302ms building triangulations from scratch for them.
- 耳切法的许可证:Meisters 1975 证明任何超过 3 个顶点的简单多边形至少有两个互不重叠的耳朵(可一刀切下的凸角三角形),于是一定能拆完得到 $n-2$ 个三角形。isEar 测试 = 凸角($2\times2$ 行列式 cross 为正)+ 没有其他顶点严格落在三角形内。有洞的(1.1 万个,天井、林中空地)要先搭桥:取洞最右点 $m$ 向右发射线,命中边取更右端点 $P$,若三角形 $mIP$ 内没有边界顶点则 $m$–$P$ 是安全桥,否则连到最近的凹点(Eberly 办法)。地图数据还贡献两个坑:整数网格上射线经常正穿顶点;院子贴外墙只共一个点时根本不需要桥。The license for ears: Meisters 1975 proved every simple polygon with more than 3 vertices has at least two non-overlapping ears, so clipping always finishes, at $n-2$ triangles. isEar = convex corner (positive 2x2 determinant cross) plus no other vertex strictly inside the corner's triangle. Holes (11,345 — courtyards, forest clearings) get bridged into one ring first: cast a ray right from the hole's rightmost vertex m, take the further endpoint P of the first hit edge; if no boundary vertex sits in triangle mIP the bridge m-P is safe, else connect to the nearest dent (Eberly's scheme). Map data adds two traps: integer grids make rays pass exactly through vertices, and a hole touching the outer wall at a single point needs no bridge at all.
- 时间阶梯:朴素耳切 1119ms → 只测凹点(引理:若三角形内有顶点,里面必有凹点;2810 万次测试从 3.53 亿点降到 1.85 亿点)882 → 凸形捷径 880 → zig-zag 长条 762 → 分桶 697 → 无分支 519 → 命中打标记 489ms。成果 earstrip:单头文件 C++、ISC、与 earcut 同签名的 npm WASM,比 earcut.hpp 快 14%,比 earcut.js 快 1.4–2.1 倍。但最大的 1,123 个多边形(257+ 顶点)仍然交给 Delaunay(90 对 199ms)——耳测试的成本在那里随尺寸平方增长。The ladder: naive clipping 1119ms → test only reflex vertices (lemma: if anything is inside an ear candidate, a dent is — cutting 353M point tests to 185M over 28.1M tests) 882 → convex shortcut 880 → zig-zag strips 762 → buckets 697 → no branches 519 → marked hits 489ms. The artifact, earstrip: one C++ header, ISC, an earcut-compatible npm WASM build — 14% faster than earcut.hpp, 1.4-2.1x faster than earcut.js. Except the 1,123 biggest polygons (257+ vertices) still go to Delaunay (90 vs 199ms): ear tests there grow with the square of size.
- 对角线法:『基本四件套』之后最有名的证明术(2015 年旧文)Diagonalization: The Most Famous Proof Method After the Basic Four (from 2015)
- (2015 年的旧文。)Kun 曾把证明方法归纳为『基本四件套』:直接、逆否、反证、归纳——但数学里『证明方法的供应量永远在增长』:概率法、线性代数法,甚至传闻中的量子法。对角线法是四件套之后最著名的:摆出一张表,翻转对角线,造出一个被证明不在表上的对象。An evergreen from 2015. Kun once distilled proofs into the 'basic four' — direct, contrapositive, contradiction, induction — but notes that mathematics keeps minting new methods: probabilistic, linear-algebra, even a rumored quantum one. Diagonalization is the most famous beyond the four: tabulate objects, flip the diagonal, construct an object proven to be off the list.
- Cantor 的版本:假设存在双射 $f:\mathbb{N}\to(0,1)$(够用,因为 $(0,1)$ 与全体实数有双射,用 $1/x$ sketches 一下即可),把每个 $f(m)$ 的无限二进制展开写成表的一行。定义 $N$:第 $i$ 位取 $1-b_{i,i}$——逐位翻转对角线。若 $N$ 在表上、等于第 $m$ 行,则它的第 $m$ 位既是 $b_{m,m}$ 又是 $1-b_{m,m}$,矛盾。结论:无穷至少有两种大小。作者的话:『the kind of proof that blows your mind the first time you see it』。Cantor's version: suppose a bijection $f:\mathbb{N}\to(0,1)$ exists (enough, since $(0,1)$ bijects with all reals — $1/x$ sketches it), and write each $f(m)$'s infinite binary expansion as a table row. Define $N$ by flipping the diagonal: digit $i$ is $1-b_{i,i}$. If $N$ were row $m$, its $m$-th digit would be both $b_{m,m}$ and $1-b_{m,m}$ — contradiction. There is more than one size of infinity; in Kun's words, the kind of proof that blows your mind the first time you see it.
- Turing 的版本:假设 T 能判停机问题。造 metaT(P):用 T 判断 P 在自己的源码上是否停机,然后反着做。把 metaT 跑在自己身上:T 说停,它就循环;T 说不停,它就停机——两个答案都矛盾,所以『永远能检测 bug 的程序』不存在。Turing's version: assume T decides the halting problem. Build metaT(P): use T to test whether P halts on its own source, then do the opposite. Run metaT on itself: T says halts, it loops; T says loops, it halts — both answers contradict, so no program can always detect bugs.
- 对角线的形态:程序全体可数(按字典序列出、扔掉非法串),输入全体可数,而每个是否类问题对应表的一行(无穷位串)。问题不可数、程序可数 ⇒ 不可解问题必然存在——同一条对角线,两次出刀。Reading it as diagonalization: programs are countable (lex order, discard invalid strings), inputs are countable, and each yes/no problem is one row of an infinite bit table. The problems outnumber programs — unsolvable problems must exist. One diagonal, two cuts.
程序员随想A Programmer's Reflections
- 1978 年,Dijkstra 论『自然语言编程』的愚蠢Dijkstra, in 1978, on the Foolishness of Natural Language Programming
- 这是 1978 年的 EWD667,今天读却像在场:从计算机最早年代起,人们就抱怨机器的『严格服从』,想要自然语言界面。高级语言诞生的功劳是把错误从『跑出错误答案』变成『弹出错误信息』——但他补了一刀:『some equate ease of programming with ease of making undetected mistakes』。EWD667 is from 1978, yet reads like this morning's thread: since computing's earliest days people blamed the machine's 'strict obedience' and wished for natural-language interfaces. High-level languages earned their place by turning mistakes into error messages instead of wrong answers — but he adds: some equate ease of programming with ease of making undetected mistakes.
- 核心质疑:换界面并不是在重分一份固定的工作量。人机协作的总功不是常数,不能指望把工作从人这边挪到机器那边就完事——一次改动可能让两边都更累。所以他偏好『窄接口』。The core doubt: changing the interface is not reallocating a fixed amount of work. Cooperation across the human-machine boundary has no constant total you can shift from one side to the other — a change can make both sides work harder. Hence his preference for narrow interfaces.
- 证据取自数学史:希腊数学沦为语言与图像活动后陷入停滞;阿拉伯的代数(algebra)退回修辞后枯死;现代世界恰恰是靠有意识设计的形式符号系统(Vieta、Descartes、Leibniz、Boole)起飞。形式文本的美德:只需几条简单规则就能做演算,同时把母语里『看不出是胡说』的陈述挡在门外——自然语言的『自然』,正是指这种胡说而不显然的能力。His evidence is the history of mathematics: Greek mathematics stalled once it became a verbal-pictorial activity; Muslim algebra died returning to rhetoric; the modern world launched precisely on consciously designed formal symbolisms (Vieta, Descartes, Leibniz, Boole). The virtue of formal texts: a few simple rules suffice for the manipulations, while statements whose nonsense is not obvious — natural language's signature talent — are locked out.
- 反转收尾:学形式语言不是负担而是特权——『school children can learn to do what in earlier days only genius could achieve』。反事实:若自然语言从一开始就是接口,计算机科学会变成一门要靠千年才爬得出来的黑暗艺术。他的直觉结语:用自然语言可编的机器,『as damned difficult to make as they would be to use』。The inversion: learning formal languages is a privilege, not a burden — school children can now learn to do what earlier only genius could achieve. The counterfactual: had natural language been the interface from the start, computer science would have become a black art taking millennia to bootstrap out of itself. His gut feeling, closing: machines programmable in natural tongues are as damned difficult to make as they would be to use.
- 软件慢是因为设计烂,不是因为语言慢Software Is Slow Because of Bad Design, Not Slow Languages
- 靶子:『让 AI 把慢程序用 Rust/C 重写就快了』。他的第一个反例是 Amdahl 定律——多数程序受 I/O 支配:CRUD 应用里数据库查询约占请求时间一半,那么其余部分无论快 50 倍还是 100 倍,总收益封顶 1.5–2 倍;curl 比你快 100 倍,你从未感觉过,因为你没在等它。The target: 'have AI rewrite the slow program in Rust/C.' First counterexample is Amdahl: most programs are I/O-bound — in CRUD apps database queries eat about half of request time, so no matter whether the rest runs 50x faster, the total ceiling is 1.5-2x. curl is 100x faster than you and you have never noticed, because you were not waiting for it.
- 第二个理由:慢语言的 CPU 重活早就外包给快库了——Python 的矩阵乘在 numpy/GPU 里跑,markdown 渲染用的是 cmark-gfm。推倒重写打不过已经调到死的库。他的 AssemblyScript 重写 tiktoken 快了 5 倍,但他自己承认:收益大概率来自去掉正则、重新设计,而不是换语言。Second reason: slow languages have long delegated their CPU-heavy work to fast libraries — Python's matrix multiplies run in numpy/GPU, markdown renders through cmark-gfm. A rewrite cannot beat already-optimized kernels. His own AssemblyScript rewrite of tiktoken ran 5x faster, but he grants the gain arguably came from dropping the regex and redesigning, not from the language.
- 第三个理由:就算真 CPU-bound,主导因素仍是设计。引 Cantrill 2018 年的轶事:随手写的 Rust 比精心调优的 C 还快 30%,因为把 BST 换成了对缓存友好的 B-tree。他自己的加速清单全是重设计:缓存慢 API、转后台/异步、并行化、把 N+1 并成单查询、重写 SQL、砍掉不需要的取数。Third reason: even CPU-bound work is dominated by design. He cites Cantrill's 2018 anecdote — careless Rust beat carefully optimized C by 30% because a BST became a cache-friendly B-tree. His own speed-up list is a redesign list: cache slow APIs, background/async, parallelize, fold N+1 into one query, write better SQL, stop fetching what you don't need.
- 反直觉收尾:高级语言恰恰是看得见 N+1 的地方;换成汇编优先,这些设计罪就会藏进指令流。结论:让 agent 先 profile、找热点、重新设计程序做什么——重写很少是答案;真要重写,为可移植性和可维护性,不是为快。The counterintuitive close: high-level code is exactly where N+1 queries stay visible; in assembly-first code those design sins hide in the instruction stream. So ask agents to profile, find hotspots, and redesign what the program does. Rewrites are rarely the answer — and when they are, do it for portability and maintainability, not for raw speed.
- UUIDv7 没有你以为的三个性质UUIDv7 Doesn't Have the Properties You Think It Does
- 市场卖三个性质:ID 单调递增、内嵌创建时间戳、不可猜。Alexander:RFC 9562 只严格保证唯一性(防碰撞),后两个在任何合规实现里都不成立。The marketed trio: monotonic IDs, embedded creation timestamps, unguessability. Alexander's claim: RFC 9562 strictly guarantees only uniqueness (collision-resistance); the other two hold nowhere, in no compliant implementation.
- 时间戳不等于创建时间。RFC 原文:『Implementations MAY alter the actual timestamp』,并且不要求与真实时钟的接近程度。演示:Python 3.14 标准库 uuid7() 遇到时钟回拨一小时——生成器拒绝让时间戳倒退,改为自增:连续 ID 的差值从 3695 涨到 3994 毫秒,负载越高发散越大。Python 维护者的答复:合规,是『有缺陷的系统』而非 bug。The timestamp is not the creation time. The RFC says outright: implementations MAY alter the actual timestamp, and requires no closeness to the real clock. Demo: Python 3.14's uuid7() when its clock jumps back an hour — the generator refuses to let timestamps go backwards and increments them instead: successive IDs drift from 3695 to 3994 milliseconds apart, diverging further under load. The Python devs' verdict: RFC-consistent; the system, not the library, is flawed.
- 跨节点单调性从 1970 年代就被证明不可能:时钟不确定 ⇒ 单靠时间戳无法排序——向量钟正是这个认识的产物。他的原句:『Timestamps are only time-ordered if you know what time it is and you don't know what time it is.』就算单节点:毫秒精度不带计数器,紧循环里就能产同毫秒乱序 ID;而且几乎没人把『上次用过的时间戳』持久化过重启(他查了好几个实现)。附带代价:URL 里的时间戳泄漏账号创建时间这类元数据。Cross-node monotonicity was proven impossible in the 1970s — clock uncertainty means timestamps alone cannot order events, which is exactly what gave birth to vector clocks. His line: timestamps are only time-ordered if you know what time it is and you don't know what time it is. Even single-node: a millisecond timestamp without a counter yields out-of-order IDs inside a tight loop, and almost no implementation persists the last-used timestamp across restarts (he checked several). Bonus cost: a timestamp in a URL leaks metadata like when the account was created.
- 实用建议:把 UUIDv7 想成『几个好主意的混装,细节留给实现自由发挥』,对任何生成器做六问:合规吗?额外承诺了什么?极限在哪?依赖什么假设(准确时钟)?什么情况下会擅自改时间戳?到底可不可猜?Practical advice: treat UUIDv7 as a mash-up of good ideas whose details implementations choose freely, and ask any generator six questions: RFC-compliant? what extra guarantees? what limits? what assumptions (an accurate clock)? when does it alter timestamps? how guessable?
- int 3 都当调试断点用了,x86 为什么还要专门发明 ud2?Why Does x86 Need ud2 When int 6 Is Right There?
- 现象:ud2 和 int 6 都是两个字节,都触发『无效操作码』(向量 6)——那为什么要多发明一条指令?Chen 的答案藏在 fault 与 trap 的语义差别里:#UD 是一个 fault——异常帧里压栈的是出错指令自己的地址,fault 的语义是『先修好再重试这条指令』(缺页、访问违例都是这种);int 6 是一个 trap——报告的是下一条指令的地址,trap 的语义是『这件事已发生,继续往下』。The puzzle: ud2 and int 6 are both two bytes and both raise 'invalid opcode' (vector 6) — so why invent an instruction? Chen's answer lives in the fault/trap distinction: #UD is a fault — the exception frame carries the address of the faulting instruction itself, because faults mean 'repair the situation and retry this instruction' (page faults, access violations); int 6 is a trap — it reports the next instruction, because traps mean 'this already happened, carry on'.
- 于是用 int 6 冒充 #UD,是一个伪装成 fault 的 trap:处理程序按定义期望 CS:EIP 指着那条无效操作码,实际指着的是后面一条完全合法指令——比如恰好在那儿的 xor eax, eax——它没法知道指令到底违不违法。So a fake #UD raised via int 6 is a trap wearing a fault's clothes: the handler is defined to inspect the instruction at the pushed CS:EIP and expects an invalid opcode — but finds whatever legitimately follows, say a harmless xor eax, eax.
- 『事后查看』救不回来:异常帧只有 CS:EIP,没有『这是谁的锅』的标记。向前回看更处处是坑:紧跟在 CD 06 数据字节之后的合法跳转目标、int 6 后面紧跟着真 ud2 的代码、NX 之前无法区分代码和数据,而在旧 CPU 上仿真缺失指令的处理程序,本来就必须看到真正的 faulting opcode。Looking around afterward cannot rescue it: the frame carries only CS:EIP, with no flag saying whose fault this is. And scanning backwards is a minefield — legitimate jump targets landing right after CD 06 data bytes, int 6 immediately followed by a real ud2, code-versus-data indistinguishable before NX, and emulators of missing instructions on older CPUs that genuinely need the real faulting opcode.
- ud2 因此保住了存在价值:给了编译器一个定义良好的『在这里抛 #UD』,80186 起就能用,还不占用 Intel 将来想定义的 opcode 空间。保护模式下反正所有操作系统都把 int 6 对Ring 3 关在门外——这个答案顺带解释了两个接口为何各归各位。Hence ud2 earns its opcode: a defined way for compilers to say 'raise #UD right here', working on every CPU from the 80186 up, without burning encoding space Intel wants later. (In protected mode, every OS denies int 6 to user mode anyway — which is why the interface split stuck.)
哲学与生活Philosophy & Life
- 摩擦学家:没有摩擦的世界,是没有进步的世界A Tribologist on Why a Frictionless World Is a World Without Progress
- 作者是摩擦学家(tribologist)——职业生涯既给喷气发动机和汽车减摩擦,也琢磨怎么增加摩擦(刷牙去牙垢)。她由此重读技术史:摩擦是抵抗运动的力,凡有运动处皆有;而轮子这个『减摩擦』的发明恰恰依赖静摩擦才推得动——在冰面上打转,正是『没有阻力的轮子=原地空转』。The author is a tribologist — a career spent reducing friction in jet engines and cars, and also increasing it (scraping plaque off teeth). That double bookkeeping lets her reread technology's history: friction is the force resisting motion, present wherever anything moves; and the wheel, the great friction-reducer, only moves you because of static friction — spin on ice and you go nowhere: a wheel without resistance is a wheel spinning in place.
- 罗马圆形剧场的麻烦:车轮与车轴的摩擦把部件烧到发光(贺拉斯《颂歌》记下过这个),于是涂 axungia 动物油脂——罗马人用的已是苏美尔人的知识:油脂比水滑。但油过热会起火,解法是泼水降温:古代的进站维修。维京人:货船宽船体用更大的形状阻力换稳性;长船瘦长把阻力削到最低求快;而搭接(clinker)铆接的船板虽增加阻力,却让整个船身能在风浪里扭曲Flex——『宁可慢一点,也不要翻』。Rome's amphitheatre: wheel-on-axle friction heated chariot parts until they glowed (Horace recorded it in the Odes), so they greased with axungia, animal fat — knowledge the Sumerians already held, that fats lubricate better than water. Overheated grease caught fire, so crews splashed water on the cars: the ancient pit stop. The Vikings: wide cargo hulls bought stability with extra form drag; slender longships minimized drag for speed; and clinker-built overlapping planks added drag yet let the whole hull twist and flex through storms — trade a little speed to not capsize.
- 1920 年代克莱斯勒:Breer 让 Earnshaw 去请教 Orville Wright,用风洞造出水滴形 Airflow——商业上是失败之作,却革命了汽车设计,风洞从此是行业标准。摩擦又极其『讲究』:随速度、受力、温度、环境变,而摩擦本身又改变温度——她的博士实验室里,极端测试的摩擦热到让钢件变色。Chandrasekhar 的动力学摩擦(引力拖曳)甚至活到今天:2024 年港中文研究者发现,只有给黑洞周围加上暗物质,恒星轨道时间才对得上。1920s Chrysler: Carl Breer had William Earnshaw consult Orville Wright and wind-tunnel a teardrop — the Airflow flopped commercially and revolutionized car design anyway. Friction is also persnickety: it shifts with speed, load, temperature and environment, and frictional heating changes the temperature — in her PhD lab, extreme tests heated steel until it changed color. Chandrasekhar's dynamical friction (gravitational drag) is still doing work: in 2024, Hong Kong researchers found star-orbit timings only matched after inferring dark matter around a black hole.
- 落点是 William James 的一句:生命建立在『self-governing resistance of the ego to the world』之中——每一项进展都生产新的摩擦,进步就是走进需要新理解的地域。全文的浓缩:ease without resistance 只是空转的运动;没有阻力的世界,没有前进。The landing is William James: life is built in the self-governing resistance of the ego to the world — every advance manufactures new friction, and progress is moving into territory that demands new understanding. Ease without resistance is motion without progress.
- 『必须扔掉你的人生,才能赢回它』:海葵、恐惧与勇气的重定义One Must Throw One's Life Away to Gain It: Fear, Rewritten
- Popova 从 Kafka 那句『one must throw one's life away in order to gain it』起头,讲佩玛·丘卓(Pema Chödrön,美国出生的藏传佛教尼师)1997 年的书 When Things Fall Apart:丘卓重新定义绝望——呼应加缪『没有对生命之绝望,就没有对生命之爱』——而出路是:与生命为友,从与这个恐惧的自己为友开始。Popova opens with Kafka's line — one must throw one's life away in order to gain it — and enters Pema Chödrön (American-born Tibetan Buddhist nun) and her 1997 book When Things Fall Apart, which reframes despair in echo of Camus' 'no love of life without despair of life': befriending life begins by befriending this frightened self.
- 恐惧是普遍的:连海葵被碰一下都会收缩。『It is not a terrible thing that we feel fear when faced with the unknown… Fear is a natural reaction to moving closer to the truth.』而方法简单到残忍:待在原地,不逃——『Things become very clear when there is nowhere to escape.』Fear is universal — even a sea anemone closes when touched. It is not a terrible thing that we feel fear when faced with the unknown; fear is a natural reaction to moving closer to the truth. And the method is brutally simple: stay where you are, don't escape — things become very clear when there is nowhere to escape.
- 于是勇气被重定义:不是没有恐惧,而是与恐惧相亲。用恐惧来拆掉熟悉的结构——丘卓说是『a complete undoing of old ways of seeing, hearing, smelling, tasting, and thinking』;你抱着不放的那些理想,需要被『再往前迈一步』的勇气不断击落。崩解不是事故的报告,是转化的收据。Hence courage, redefined: not the absence of fear but intimacy with it. Use fear to dismantle the familiar structures — a complete undoing of old ways of seeing, hearing, smelling, tasting, and thinking — and let the courage to step further keep shooting down the ideals you hold onto. Falling apart is not the accident's report; it is transformation's receipt.
工具角Tools Corner
- handwired:把普通 JavaScript 变成精确、免训练、可求导的神经网络handwired: Plain JavaScript as an Exact, Training-Free, Differentiable Net
- if-else、循环、状态 → 矩阵乘 + ReLU:Math.max(0,x) 就是 ReLU;对整数 a,判断 a>4 写成 above4 = max(0,a-4) - max(0,a-5)(一个 0/1 指示函数),然后 result = above4*10 + (1-above4)*12——两个分支都算,ReLU 替你选。全部收集成一个巨型 matmul,在 JS 或 WebGPU 上跑。if-else, loops and state become matmul + ReLU: Math.max(0,x) is ReLU; for integer a, the test a>4 is written above4 = max(0,a-4) - max(0,a-5), a 0/1 indicator, then result = above4*10 + (1-above4)*12 — both branches compute and the ReLU picks. Everything is collected into one giant matmul, run on JS or WebGPU.
- 后果:程序端到端可求导;权重是人手写的,所以不用训练、结果精确;GPU 上融合、稀疏化、重排这些技巧对两个原子的活儿如鱼得水。玩法:冻结解冻随便切—— unfreeze 权重去训练;把冻结的程序接到通用网络上(nanoGPT 从此一边演莎士比亚一边演你的 UI);单线程 JS 吃上 GPU 并行——JSON 搜索 demo 在 10 万文档上只要毫秒。MIT,2.0k stars。Consequences: the program is differentiable end to end; the weights are hand-written, so there is no training and results are exact; GPU tricks — fusion, sparsity, reordering — love two primitives. Switches to play with: unfreeze the weights and train; attach a frozen program to a generic net (a nanoGPT that does both Shakespeare and your UI); give single-threaded JS GPU parallelism — a JSON-search demo scans 100k documents in milliseconds. MIT, ~2.0k stars.
- Uberblok:ZFS 盘上那圈 uberblock 的交互式博物馆Uberblok: An Interactive Museum of the ZFS Uberblock
- uberblock 是每块盘上的一个小记录:最新事务组(txg)号加 ub_rootbp 指针,指向整个池的元数据树。ZFS 从不覆写——txg 每隔几秒提交一次,写进一个 128 KiB 的环形槽位(512B 扇区则 128 个槽,4KiB 扇区 32 个,位置 = txg mod 槽数):写到一半断电,上一个 uberblock 还完好。导入池时:读遍所有槽,扔掉 magic(0x00bab10c,读作 oo-ba-bloc)和校验和不过的,取 txg 号最高的有效者。An uberblock is a small record on every disk: the latest transaction-group (txg) number plus ub_rootbp, the pointer into the pool's whole metadata tree. ZFS never overwrites — every few seconds a txg commits into a ring of slots (a 128 KiB ring: 128 slots on 512B sectors, 32 on 4KiB; position = txg mod slot count), so a power cut mid-write leaves the previous uberblock intact. Pool import reads every slot, discards entries failing magic 0x00bab10c (pronounced oo-ba-bloc) and checksum, and keeps the highest valid txg.
- 页面把每张图旁都标注了三段 OpenZFS zfs-2.4.4 真实源码(struct uberblock 的字段注释、vdev_uberblock_sync 里 multihost 的 MMP 挪槽说明、vdev_uberblock_load_done 的比较逻辑),3D 环可视、ashift 可调、自动播放提交动画。Every figure is annotated with three excerpts from real OpenZFS zfs-2.4.4 source — the struct uberblock fields, vdev_uberblock_sync's multihost MMP slot dance, vdev_uberblock_load_done's compare-highest — inside a 3D ring view with adjustable ashift and an auto-playing commit animation.
- HatchZip:从后往前解压,把空间需求砍掉一半HatchZip: Extract From the Back to Halve the Disk You Need
- 问题很日常:180GB 的归档要解压出 200GB,WinRAR、7-Zip、unzip 会当场要你 380GB。HatchZip(Rust,Win/mac/Linux 二进制)的做法是从归档的尾部开始解,每解完一个成员就把它从压缩档里截断删掉——刚释放的空间马上喂给后面的文件,总需求降到约 200GB。The everyday problem: a 180GB archive expanding to 200GB makes WinRAR, 7-Zip and unzip demand 380GB on the spot. HatchZip (Rust; Win/mac/Linux binaries) extracts from the end of the archive and truncates each finished member off the file as it goes — space reclaimed the moment it is freed — bringing the requirement down to roughly 200GB.
- 工程细节诚实:动手改磁盘之前先预检输出装不装得下、全程保留 free-space 安全边际、随时可停可崩可续;支持 ZIP/7z/tar/tar.gz 和分卷。演示表格:220MiB 的盘上 unzip 死在第 6 个文件(共 21 个),HatchZip 完整解出且逐字节一致;380MB 的 solid 7z 用了 0.64 秒。Honest engineering: it pre-flights whether the output will fit before mutating anything, keeps a free-space safety margin throughout, and is stop/crash-resumable; supports ZIP, 7z, tar, tar.gz and split volumes. The demo table: on a 220MiB disk unzip dies at file 6 of 21 while HatchZip finishes byte-identical; a 380MB solid 7z takes 0.64s.
- Dovepass:在旧金山,按你的精确航线查这趟无人机飞不飞得合法Dovepass: Is This Exact Drone Path Legal to Fly in San Francisco?
- 地图上点起飞点和目的地,选机型、巡航高度、电池余量,它逐层查:FAA 空域与机场区、TFR 临时禁飞、巨人队主场比赛、SF 市立公园、Presidio、国家公园土地(Ocean Beach、Crissy Field、恶魔岛都在)、Candlestick、监狱、金门大桥,再到 400 英尺下地形与建筑的净空、风况与电池、视距线距离——用摄像头或 FPV 看是不算数的,那要申请 waiver。Pick takeoff and destination on the map, choose the drone, cruise height and battery reserve, and it checks layer by layer: FAA airspace and airport zones, TFRs, Giants home games, SF city parks, the Presidio, national-park land (Ocean Beach, Crissy Field, Alcatraz), Candlestick, jails, the Golden Gate Bridge — plus terrain and building clearance under 400 feet, wind, battery, and line-of-sight distance, where looking through a camera or FPV does not count without a waiver.
- 输出是:结论 + 编号的『这里会发生什么』航点 + 侧视高度剖面图 + 可导出的 DJI 应用文件、可打印的飞行卡。最有分寸感的是诚实:它明确列出自己不查的规则(私人产权、隐私、拍摄许可),并且每个数据源都标注『最近一次已读』日期。Output: a verdict, numbered 'what happens here' waypoints, a side-view height chart, an exportable DJI-app file and a printable flight card. The most striking part is the honesty: rules it does NOT check (private property, privacy, filming permits) are listed explicitly, each source tagged with a 'last read' date.
- reylo:零 codegen,让 .sql 文件在 TypeScript 里自带全类型reylo: Fully Typed .sql Imports in TypeScript, Zero Codegen
- 用法:把 get_author.sql 丢进项目——里面写着 :id::int 参数——然后 import getAuthor from './get_author.sql',得到的函数签名直接是 ({id:number}) => Promise<{id:number; name:string; post_count:number} | null>。没有任何 codegen 步骤:类型由 SQL 自身对着一个跑着的开发库的真实 schema 解出来,底层靠 TypeScript 7.1 的 content mappers(beta;需要 Node 24)。The usage: drop get_author.sql into the project — with a :id::int parameter written in it — and import getAuthor from './get_author.sql'; the function arrives typed as ({id:number}) => Promise<{id:number; name:string; post_count:number} | null>. No codegen step anywhere: the types are derived from the SQL itself, checked against a live dev database's real schema, riding on TypeScript 7.1 content mappers (beta; needs Node 24).
- 后果:列名拼错、参数少写、表被删——tsc 和编辑器当场报错;类型只存在于 SQL 这一处,所以 agent 不会拿着过期的手抄类型写代码,漏改的调用方由类型检查兜底。Postgres/MySQL/SQLite,驱动自带即可(pg、postgres.js、mysql2、better-sqlite3、Bun.sql、Cloudflare D1)。Consequences: a misspelled column, a missing parameter, a dropped table become tsc and editor errors; the types live in exactly one place, so agents never work from stale hand-copied definitions, and missed callers surface at type-check time. Postgres, MySQL, SQLite — bring your own driver (pg, postgres.js, mysql2, better-sqlite3, Bun.sql, Cloudflare D1).