每日科技文摘 · 2026-10-25Daily Tech Digest · 2026-10-25
发布于 2026-10-25Published 2026-10-25
今日深读Today's Deep Read
AI 写了 18 个月能做的活之后,人类的工作方式要变成『招一队临时工』After AI Got to Doing 17 Hours of Work per Prompt, Our Job Becomes 'Hiring a Crew on the Fly'
先说清楚这篇东西在比什么:Mollick 的第一本 AI 书《Co-Intelligence》出版于 2024 年初,这本《Co-Existence》是 2026 年 10 月出的,正好 30 个月。他没有拿新闻比新闻,而是把同一类指标前后拉通:当时最好的单一模型是 GPT-4,现在已经轮换过 20 个'第一名',而比 GPT-4 发布时强的模型总数到了 180 个——其中 19 个可以直接跑在手机上。First, what this piece is actually comparing. Mollick's first AI book, Co-Intelligence, came out in early 2024; Co-Existence lands this October 2026 — exactly 30 months later. He doesn't pit news against news; he lines up the same metrics across that gap. The single best model used to be GPT-4; the 'leader' has since rotated through twenty different models, and 180 models now outperform GPT-4 as it was at release — nineteen of them running directly on a phone.
最陡的曲线是 METR 的'任务时长'基准:AI 单次提示能独立完成的、有 50% 成功率的人类工作时间。从 GPT-4 发布到该基准停止可测,这条线翻动了 8 倍:2024 年是 4 分钟的任务,2026 年 4 月交稿时是 17 小时——然后 METR 直接说量不动了,后续估算甚至到 17 周。同时价格往反方向走:同一道考研级难题,单次答对的 API 成本从 30 美分掉到 0.04 美分。能力指数级上去,成本指数级下来,两条线同时发生。The steepest curve is METR's task-length benchmark: how much human work — measured in duration — an AI can complete from a single prompt at least 50% of the time. From GPT-4's launch to the point where the benchmark stopped being measurable, that number doubled eight times over: four-minute tasks in 2024, and 17 hours when his draft went to press in April 2026 — after which METR simply declared it couldn't measure anymore, with later estimates running to 17 weeks. Meanwhile cost went the opposite way: the price of a single correct answer to a graduate-level problem fell from 30 cents to 0.04 cents. Capability compounds upward, cost compounds downward, happening at the same time.
但能力曲线是锯齿形的:长文写作一直弱,数学题从差到超人。所以 Mollick 的真正论点是'协作方式'变了。他原来有两个词:centaur(人机分工,各管一段)和 cyborg(人机混合,你一直在回路里)。现在加第三个词:conjurer——你不再在回路里,你是召唤者:把活分派给 agent,只看结果,反复说'再做好一点'。这篇里他自己就是 demo:图表全部是 agent 做的,agent 还发现了他把'28 个月'算错成标题'30 个月'。But the capability curve is jagged: long-form writing has stayed weak, while math went from poor to superhuman. So Mollick's real claim is about how we collaborate. He'd previously named two modes — centaur (human and AI each handle their own segment) and cyborg (blended, you stay in the loop). Now he adds a third: the conjurer, who is out of the loop entirely — summoning agents, assigning the work, judging only the results, and saying 'make it a bit better.' The post is itself a demo: he made every chart with agents, and one of them caught him writing '28 months' where his title says '30 months.'
最后他留了一句值得咂摸的:'这只是我们谈论 AI 的最低点。'能力越大,人类要自己决定的事越多——什么时候把活交给机器、什么时候完全别碰。这本书赌的就是:理解了这两条曲线(指数增长 + 锯齿形前沿)的人,会被现状少惊讶一点。He closes with a line worth chewing on: 'This is the least we will ever talk about AI.' As capability grows, the human's job becomes choosing when to hand work to machines and when not to touch it at all. The book's bet: the people who understand these two curves — exponential gains on a jagged frontier — will be less surprised by what keeps happening.
能带走什么:如果你判断 AI 项目该怎么做,别问'哪个模型最强',问两件事——'我的活处于哪段锯齿上'和'我是 centaur、cyborg 还是 conjurer'。角色选错,模型再强也白搭。What to take away: when you're deciding how to structure AI work, don't ask 'which model is the strongest.' Ask two things — 'which part of the jagged frontier is my task on?' and 'am I the centaur, the cyborg, or the conjurer?' Get the role wrong and the best model in the world won't save you.
AI 思考AI Thoughts
- Claude Code 一小时独立开公司,靠的是『忘事后看纹身』式记法Claude Code Built a One-Person Business in an Hour, Powered by 'Tattoos After Amnesia'
- 问题:AI 上下文窗口有顶,长活做到一半就'失忆'——怎么让它连续干几个小时还不忘事?The problem: AI context windows have a ceiling, so long tasks lose memory mid-way. How do you keep it going for hours?
- 关键想法一:compacting。窗口满时停下来把进展写成便签,清窗后由新版本读便签继续——Mollick 的比喻是《记忆碎片》主角醒来看自己身上的纹身。Idea one: compacting. When the window fills, the agent writes notes on its progress, clears the window, and a fresh instance reads the notes and continues — Mollick's analogy is the amnesiac in Memento reading his own tattoos.
- 关键想法二:Skills。长指令太占窗口,改成一堆'技能包',AI 判断需要时再加载,像 Neo 上传功夫——按需换知识而不是一直举着全部说明书。Idea two: Skills. Long prompts eat the window, so they become 'skill packs' the AI loads when it decides it needs them — like Neo downloading kung fu, swapping knowledge on demand instead of holding every manual up at once.
- 关键想法三:subagents。大模型当包工头,把简单活分派给便宜快的模型并行做,各带各的上下文窗口。Idea three: subagents. The big model acts as foreman, delegating easy jobs to cheaper, faster models that run in parallel with their own context windows.
- 能带走什么:agentic 工具的强大不在模型本身,而在'脚手架'(harness)——这些机制正是 AI 从聊天框走向干真活的门槛。Takeaway: what makes agentic tools powerful isn't the model itself but the harness around it — and these mechanisms are exactly what moved AI from chatbox to real work.
- AI 工程师的五个坑:第一个就是『拿 AI 当锤子』Five Pitfalls of AI Engineering, Starting With 'AI Is a Hammer, Not Every Job Is a Nail'
- 坑一:拿生成式 AI 解决普通优化问题。她见过团队用 LLM 排家电用电表,她一问'那直接把洗衣和充电排在电价最低的时段呢?'——贪心调度可能就够了,人家再没下文。Pitfall one: reaching for generative AI on a plain optimization problem. A team asked an LLM to schedule a home's energy use; when Huyen asked 'have you tried just running the heavy loads during cheap hours?' — the greedy rule might already work — they never followed up.
- 坑二:把'产品烂'当成'AI 烂'。三个案例:会议纪要用户根本不在乎摘要长度、只在乎自己的行动项;LinkedIn 的用户要的不是'你匹配度很低'(对但没用),而是缺口在哪、怎么补;Intuit 的用户讨厌的是打字——加了可点选的问题后体验才起来。Pitfall two: calling a bad product a bad AI. Three examples: meeting-summary users didn't care about summary length, only their own action items; LinkedIn users wanted 'here's the gap and how to close it,' not the correct verdict 'you're a poor fit'; Intuit users hated typing — clicking suggested questions fixed the experience.
- 坑三:起步太复杂。能用直接 API 解决就上 agent 框架,能用词频检索就上向量库,能用提示就上微调——每层抽象都挡掉可调试性,还带来别人的 bug。Pitfall three: starting too complex. Direct API calls before agent frameworks, term-based retrieval before vector databases, prompting before fine-tuning. Each abstraction hides debuggable detail and imports someone else's bugs.
- 坑四:被早期 80% 骗了。LinkedIn 一个月做到 80%,剩下 15% 又花了四个月;'0→80' 和 '80→90' 常常一样难。Pitfall four: over-reading the early 80%. LinkedIn hit 80% in a month and needed four more months to pass 95%; '0 to 80' and '80 to 90' can take just as long.
- 能带走什么:同一套模型大家都有,AI 产品最后赢在工程判断力——知道什么时候不用、怎么起步最小、预期要多长。Takeaway: since everyone uses the same models, AI products now win on engineering judgment — knowing when not to use, starting minimal, and expecting the long tail to be long.
- 用声音给两台手机联机:Willison 的 vibe-coded RTS 学到什么Wiring Two Phones Together by Sound: What Willison's Vibe-Coded RTS Taught Him
- Willison 重做 1995 版《红色警戒》式 RTS,全程 vibe-coded:12 个主要迭代、321 次 commit 全是 Claude Code 写的,他自己几乎没读 TypeScript 源码。关键学习不是『AI 能写游戏』,而是那句让他尴尬的话——让 Claude『Make it a LOT more fun』,游戏才真正好玩。把『好玩』当成可下放的规格,比逐行调手感有效。Willison rebuilt a 1995-style Red Alert RTS, fully vibe-coded: 12 major iterations, 321 commits all written by Claude Code, and he barely read the TypeScript himself. The key learning wasn't 'AI can write games' but the line that embarrassed him — he had to tell Claude 'Make it a LOT more fun' for the game to actually be fun. Delegating 'fun' as a spec beats hand-tuning the feel.
- 最惊艳的功能:两台手机在麦克风范围内联机。用『声音同步游戏状态』代替网络——一台手机把状态编码成声波(延续他早年的 Chirp Pong 实验),另一台收音解码。没有后端、没有账号,声波就是总线。The headline feature: two phones link up over the microphone. He syncs game state via sound — one phone encodes state into audio (extending his earlier Chirp Pong experiments), the other decodes it. No backend, no accounts; the sound wave is the bus.
- 这暴露了 AI 时代一种新玩法:把『不可思议的物理细节』(声波编码/解码、跨设备同步)直接交给 agent 去实现,人只做两件事——定目标(好玩、可联机)+ 验收。人退到『规格制定者』的位置,而不是实现者。This exposes a new pattern in the AI era: hand 'impossible physical details' (audio codec, cross-device sync) to the agent; the human does only two things — set the goal (fun, linkable, mobile-friendly) and accept the result. You retreat to 'spec-setter', not implementer.
- 对程序员的启示:vibe-coding 的瓶颈从『写得出来』变成了『说得清』。你能不能把『更酷、联机、移动端能玩』翻译成 agent 一次次迭代都稳得住的规格,比你的编码能力更决定产出上限。The lesson for programmers: in vibe-coding, the bottleneck shifts from 'can you write it' to 'can you say it clearly.' Whether you can translate 'cooler, multiplayer, playable on a phone' into a spec that the agent's iterations can stably hold matters more than your coding skill to your output ceiling.
数学之美The Beauty of Math
每日 Lean 谜题 · 周日Daily Lean Puzzle · Sunday ★★★★★★★
平方和的天花板:$S(n)\le n^2-14$,而 13 恰好踩到顶(★7)The Ceiling of Square Sums: $S(n) \le n^2-14$, and 13 Hits It Exactly (★7)
对每个正整数 $n$,设 $S(n)$ 为最大的整数,使得对每个 $k\le S(n)$,$n^2$ 都能写成 $k$ 个正平方数的和。For each positive integer $n$, let $S(n)$ be the greatest integer such that for every $k\le S(n)$, $n^2$ can be written as the sum of $k$ positive squares.
(a) 证明:对所有 $n\ge 4$,$S(n)\le n^2-14$;(a) Prove that for all $n\ge 4$, $S(n)\le n^2-14$;
(b) 找一个 $n$ 使 $S(n)=n^2-14$;(b) Find an $n$ with $S(n)=n^2-14$;
(c) 证明满足 $S(n)=n^2-14$ 的 $n$ 有无穷多个。(c) Prove that there are infinitely many $n$ with $S(n)=n^2-14$.
(IMO 1992 第 6 题,当年卷末压轴。Lean 定理:$S$ 由一个良定义性引理链先行铺垫($S_{set}$ 非空、有界、有限),结论是三个子命题的合取。)(IMO 1992, Problem 6 — the last question of the paper. In the Lean formalization, $S$ is preceded by a well-definedness lemma chain ($S_{set}$ nonempty, bounded, finite), and the theorem is the conjunction of the three sub-goals.)
Lean 形式化陈述(把 sorry 换成你的证明):The statement in Lean (replace sorry with your proof):
/-
Copyright (c) 2026 Constantin Seebach. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Constantin Seebach
-/
import Mathlib.Tactic
/-!
# International Mathematical Olympiad 1992, Problem 6
For each positive integer $n$, $S(n)$ is defined to be the greatest integer such that, for every positive integer $k \le S(n)$, $n^{2}$ can be written as the sum of $k$ positive squares.
(a) Prove that $S(n) \le n^{2}-14$ for each $n \ge 4$.
(b) Find an integer $n$ such that $S(n)=n^{2}-14$.
(c) Prove that there are infinitely many integers $n$ such that $S(n)=n^{2}-14$.
-/
namespace Imo1992P6
def is_sum_of_pos_squares (z k : ℕ) : Prop := ∃ s : (Fin k → ℕ), z = ∑ i, (s i)^2 ∧ ∀ i, 0 < s i
def S_set (n : ℕ+) := { z : ℕ+ | ∀ k, k ≤ z → is_sum_of_pos_squares (n^2) k }
/-!
The definition of $S(n)$ in the problem statement hides a lot of complexity. The following lemmas are needed to write down $S(n)$ in a well-defined way.
-/
lemma S_set_Nonempty (n : ℕ+) : Set.Nonempty (S_set n) := by
apply Set.nonempty_of_mem (x:=1)
simp_rw [S_set, is_sum_of_pos_squares]
intro k kle1
use λi => n
simp_all
lemma S_set_bounded (n) : ∀ k ∈ S_set n, k ≤ n^2 := by
simp_rw [S_set, is_sum_of_pos_squares, Set.mem_ofPred_eq]
intro k kh
let kh := kh k
simp only [le_refl, forall_const] at kh
let ⟨s,sh1, sh2⟩ := kh
rw [← PNat.coe_le_coe]
norm_cast at sh1
rw [sh1]
calc
_ = ∑ i : Fin k, 1 := by simp
_ ≤ _ := Finset.sum_le_sum fun i _ ↦ Nat.one_le_pow 2 (s i) (sh2 i)
lemma S_set_Finite (n) : Set.Finite (S_set n) := by
apply Set.Finite.of_finite_image (f:=Subtype.val)
· refine Set.finite_iff_bddAbove.mpr ?_
refine bddAbove_def.mpr ?_
use n^2
rintro y ⟨⟨y', ypos⟩, h, rfl⟩
exact mod_cast S_set_bounded n ⟨y', ypos⟩ h
· exact Subtype.val_injective.injOn
noncomputable def S (n : ℕ+) := (Set.Finite.exists_maximal (S_set_Finite n) (S_set_Nonempty n)).choose
namespace Multiset
end Multiset
namespace Nat
end Nat
abbrev imo1992_p6_b : ℕ+ := sorry
theorem imo1992_p6 : (∀ n ≥ 4, S n ≤ n^2-14) ∧ (S imo1992_p6_b = imo1992_p6_b^2 - 14) ∧ ({n | S n = n^2 - 14}.Infinite) := by
sorry
end Imo1992P6
在浏览器中挑战 ▶Try it in your browser ▶ 下载题目 .leanDownload puzzle .lean
提示Hint
先看 (a):假设 $S(n)\ge n^2-13$,那么 $n^2$ 能写成 $n^2-13$ 个正平方数之和。每个正平方数至少是 $1^2=1$,而只有 $1,4,9$ 三种取值会留下『余量』——算一算这些余量的总和为什么必须恰为 $13$,而 $1,4,9$ 凑不出 $13$。再想:什么时候把四个相同的 $1$ 换成一个 $4$ 能不改变总和、把项数减少多少?Start with (a): suppose $S(n)\ge n^2-13$; then $n^2$ is a sum of $n^2-13$ positive squares. Each square is at least $1$; only squares $1,4,9$ leave 'headroom' — check why the total headroom must be exactly $13$, and why $1,4,9$ cannot add up to $13$. Then think: when does replacing four identical $1$s by one $4$ preserve the total, and by how many terms does it shorten the sum?
答案与讲解Solution & walkthrough
- 第一步(问题 (a),纯算术不等式)。把 $n^2$ 写成 $n^2-13$ 个正平方数:设其中有 $a$ 个 $1^2$、$b$ 个 $2^2$、$c$ 个 $3^2$(更大的 $s^2\ge16$ 直接导致总和超过 $n^2$)。总和展开得 $n^2=(n^2-13)+\underbrace{0\cdot a+3b+8c}_{13}$——13 必须写成 $3b+8c$,但 $b,c$ 非负时 $3b+8c\in\{0,3,6,8,9,11,14,\dots\}$,跳过了 13。矛盾。Lean:$imo1992_p6_a$ 的对应段先把 $s i<4$ 证出来($slt4$),再数 $a=|\{i:s i=2\}|$、$b=|\{i:s i=3\}|$,最后由 $13=3a+8b$ 与集合元素有限性收口。Step 1 (part a, pure arithmetic). Write $n^2$ as $n^2-13$ positive squares, with $a$ copies of $1^2$, $b$ of $2^2$, $c$ of $3^2$ (any $s^2\ge16$ blows the total past $n^2$). Expanding: $n^2=(n^2-13)+(0\cdot a+3b+8c)$, so the headroom $13$ must equal $3b+8c$ — but nonnegative $3b+8c$ takes values $0,3,6,8,9,11,14,\dots$ and jumps over 13. Contradiction. In Lean, $imo1992_p6_a$ first proves every $s_i<4$ ($slt4$), then counts $a=|\{i:s_i=2\}|$, $b=|\{i:s_i=3\}|$, and closes on $13=3a+8b$.
- 第二步(问题 (b),找 13)。『把四个 1 合并成一个 4』是万能手术:总和不变($4\times1^2=2^2$),项数减 3。从 $169=9+4+4+152\times1$(155 项 $=n^2-14$)反复做这个手术,可以把项数逐 3 降:$169\to 152\to 149\to\dots\to 9$。三个模 3 类各起一个种子:$0\bmod 3$ 类从 $N-16=153$ 项出发($9+9+151\times1$),$1\bmod 3$ 类从 154 项,$2\bmod 3$ 类从 155 项。三类合起来覆盖 $5\le k\le155$;$k=1,2,3,4$ 另有显式分解($169=13^2$、$12^2+5^2$、$10^2+8^2+2^2+1^2$、$10^2+8^2+2^2+1^2$ 一族)。于是 $S(13)=13^2-14$。Step 2 (part b, finding 13). The universal move: 'merge four 1s into one 4' preserves the sum ($4\times1^2=2^2$) and cuts the term count by 3. Starting from $169=9+4+4+152\times1$ (155 terms $=n^2-14$), repeated merges descend by 3: $155\to152\to\dots\to9$. Seed each residue mod 3: $0\bmod3$ from $N-16=153$ terms, $1\bmod3$ from 154, $2\bmod3$ from 155; together they cover $5\le k\le155$, and $k=1,2,3,4$ have explicit small decompositions. Hence $S(13)=13^2-14$.
- 第三步(问题 (c) 的关键引理:乘法封闭)。若 $N_1,N_2$ 都『完整』(所有 $k\le N_i-14$ 可表),则 $N_1N_2$ 也完整:把 $N_2$ 的 $k_2$ 项和乘以 $n_1^2$(每项乘 $n_1$,项数不变),再拆出 $N_1$ 的分解……Lean 里这就是 $sos_mul$(两列和相乘)与 $complete_mul$ 的组合:先用 $k_1k_2$ 覆盖大区间,再用 $n_1^2$ 的两平方分解把剩余小项数补齐。Step 3 (the key lemma for part c: closure under products). If $N_1,N_2$ are both 'complete' (every $k\le N_i-14$ is representable), so is $N_1N_2$: multiply each term of the $k_2$-term representation of $N_2$ by $n_1$ (term count unchanged), then patch the remaining small $k$ with a two-square split of $n_1^2$. In Lean this is $sos_mul$ (product of two sums) combined with $complete_mul$.
- 第四步(归纳到无穷)。13 完整(第二步),且完整数的乘积完整(第三步),于是 $13,13^2,13^3,\dots$ 全部完整——$imo1992_p6_c$ 就是对 $e$ 的归纳,每步 $pow_add$ 一次后套用 $complete_mul$。Step 4 (induction to infinity). 13 is complete (step 2) and the product of complete numbers is complete (step 3), so $13,13^2,13^3,\dots$ are all complete — $imo1992_p6_c$ is induction on $e$, one $pow_add$ per step, then $complete_mul$.
- 第五步(Lean 形状)。整个证明约 1000 行,但数学结构很轻:四个引理各管一段——$S_{set}$ 三件套(非空/有界/有限,让 $S$ 良定义)、$repeat\_shift$(把『合并四个 1』机械化:4 个 $i$ 换成 1 个 $2i$,项数 $-3$、平方和不变)、$complete\_iff\_sos$(把『S 达到上界』翻译成『所有 k 可表』)、$complete\_mul$(乘法封闭)。最重的计算被压到 $\mathtt{decide+kernel}$——Lean 对 $169=\dots$ 这类数字等式直接求值,数学家纸面上的『显然』在这里是编译器的活。Step 5 (the Lean shape). The proof is roughly 1000 lines but mathematically light: four lemmas, each covering one segment — the $S_{set}$ trio (nonempty/bounded/finite, so that $S$ is well-defined), $repeat\_shift$ (mechanizing 'merge four 1s': four $i$s become one $2i$, term count $-3$, square sum unchanged), $complete\_iff\_sos$ (translating 'S hits the ceiling' into 'every k is representable'), and $complete\_mul$ (multiplicative closure). The heavy numerics are delegated to $\mathtt{decide+kernel}$ — Lean evaluates equalities like $169=\dots$ outright; the mathematician's 'obviously' is the compiler's job here.
/-
Copyright (c) 2026 Constantin Seebach. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Constantin Seebach
-/
import Mathlib.Tactic
/-!
# International Mathematical Olympiad 1992, Problem 6
For each positive integer $n$, $S(n)$ is defined to be the greatest integer such that, for every positive integer $k \le S(n)$, $n^{2}$ can be written as the sum of $k$ positive squares.
(a) Prove that $S(n) \le n^{2}-14$ for each $n \ge 4$.
(b) Find an integer $n$ such that $S(n)=n^{2}-14$.
(c) Prove that there are infinitely many integers $n$ such that $S(n)=n^{2}-14$.
-/
namespace Imo1992P6
/--
$z$ can be written as the sum of $k$ positive squares.
-/
def is_sum_of_pos_squares (z k : ℕ) : Prop := ∃ s : (Fin k → ℕ), z = ∑ i, (s i)^2 ∧ ∀ i, 0 < s i
/--
Auxiliary definition: S(n) will be defined as the greatest integer of the set S_set(n).
-/
def S_set (n : ℕ+) := { z : ℕ+ | ∀ k, k ≤ z → is_sum_of_pos_squares (n^2) k }
/-!
The definition of $S(n)$ in the problem statement hides a lot of complexity. The following lemmas are needed to write down $S(n)$ in a well-defined way.
-/
lemma S_set_Nonempty (n : ℕ+) : Set.Nonempty (S_set n) := by
apply Set.nonempty_of_mem (x:=1)
simp_rw [S_set, is_sum_of_pos_squares]
intro k kle1
use λi => n
simp_all
lemma S_set_bounded (n) : ∀ k ∈ S_set n, k ≤ n^2 := by
simp_rw [S_set, is_sum_of_pos_squares, Set.mem_ofPred_eq]
intro k kh
let kh := kh k
simp only [le_refl, forall_const] at kh
let ⟨s,sh1, sh2⟩ := kh
rw [← PNat.coe_le_coe]
norm_cast at sh1
rw [sh1]
calc
_ = ∑ i : Fin k, 1 := by simp
_ ≤ _ := Finset.sum_le_sum fun i _ ↦ Nat.one_le_pow 2 (s i) (sh2 i)
lemma S_set_Finite (n) : Set.Finite (S_set n) := by
apply Set.Finite.of_finite_image (f:=Subtype.val)
· refine Set.finite_iff_bddAbove.mpr ?_
refine bddAbove_def.mpr ?_
use n^2
rintro y ⟨⟨y', ypos⟩, h, rfl⟩
exact mod_cast S_set_bounded n ⟨y', ypos⟩ h
· exact Subtype.val_injective.injOn
noncomputable def S (n : ℕ+) := (Set.Finite.exists_maximal (S_set_Finite n) (S_set_Nonempty n)).choose
/-!
We roughly follow the proof from https://prase.cz/kalva/imo/isoln/isoln926.html. Note that it is quite lacking in details.
But first some general theorems that I wish were in Mathlib.
-/
namespace Multiset
theorem map_sub_of_injective {α β : Type} [DecidableEq α] [DecidableEq β] (f : α → β) (inj : Function.Injective f) (s t) : Multiset.map f (s - t) = Multiset.map f s - Multiset.map f t := by
revert s
revert t
apply Multiset.induction
· simp
· intro a t ih s
simp only [Multiset.sub_cons, Multiset.map_cons]
rw [ih]
congr
rw [Multiset.map_erase _ inj]
theorem sum_sub {α : Type} [DecidableEq α] [AddCommMonoid α] (s t : Multiset α) (h : t ≤ s) : (s - t).sum + t.sum = s.sum := by
revert s
revert t
apply Multiset.induction
· simp
· intro a t ih s h
simp only [Multiset.sub_cons, Multiset.sum_cons]
nth_rw 2 [add_comm]
rw [← add_assoc, ih]
· rw [add_comm, Multiset.sum_erase]
apply Multiset.mem_of_le h (by simp)
· rw [Multiset.le_iff_exists_add] at h
obtain ⟨u, uh⟩ := h
rw [uh]
simp
end Multiset
namespace Nat
theorem sub_mod {a b c : Nat} (h : b ≤ a) : (a - b) % c = (a - b % c) % c := by
nth_rw 3 [Nat.mod_eq_sub_div_mul]
rw [Nat.sub_sub_right, Nat.sub_add_comm]
· exact (Nat.add_mul_mod_self_right (a - b) (b / c) c).symm
· exact h
· exact Nat.div_mul_le_self b c
theorem sub_mod_eq_add_mod {a b c : Nat} (h : b ≤ a) (cnz : c ≠ 0) : (a - b) % c = (a + (c - b % c)) % c := by
rw [← Nat.add_sub_assoc, Nat.sub_add_comm, Nat.add_mod_right]
· exact sub_mod h
· trans b
· exact Nat.mod_le b c
· exact h
apply le_of_lt
apply Nat.mod_lt
exact Nat.zero_lt_of_ne_zero cnz
end Nat
lemma S_spec (n : ℕ+) : Maximal (fun z : ℕ+ => ∀ k, k ≤ z → is_sum_of_pos_squares (n^2) k) (S n) := by
exact Exists.choose_spec _
theorem imo1992_p6_a : ∀ n ≥ 4, S n ≤ n^2-14 := by
by_contra! c
obtain ⟨n, nge, h⟩ := c
have nge : 14 < n ^ 2 := by
simp at nge
suffices 4^2 ≤ n^2 by
rw [← PNat.coe_le_coe] at this
rw [← PNat.coe_lt_coe]
apply Nat.lt_of_add_one_le
simp_all
exact Nat.le_of_add_left_le this
exact pow_le_pow_left' nge 2
have nge' : 13 < n^2 := by
trans 14
· simp
· exact nge
have c : is_sum_of_pos_squares (n^2) (n^2-13) := by
have : (n.val ^ 2 - 13) = (n ^ 2 - 13).val := by
rw [PNat.sub_coe]
simp [nge']
rw [this]
apply (S_spec n).prop (n^2-13)
rw [← PNat.coe_lt_coe, PNat.sub_coe] at h
rw [← PNat.coe_le_coe, PNat.sub_coe]
simp [nge, nge'] at h ⊢
rw [Nat.sub_lt_iff_lt_add] at h
· exact Nat.le_of_lt_succ h
· exact nge'
unfold is_sum_of_pos_squares at c
obtain ⟨s, sh1, sh2⟩ := c
have slt4 : ∀ i, s i < 4 := by
by_contra! c
obtain ⟨j, h⟩ := c
have := calc (n : ℕ)^2
_ < n ^ 2 - 14 + 16 := by
rw [← Nat.sub_add_comm]
· simp
· exact nge'
_ ≤ n^2 - 14 + s j ^ 2 := by
simp
have : 16 = 4^2 := by simp
rw [this]
apply pow_left_mono 2
exact h
_ = ∑ i ∈ Finset.univ \ {j}, 1 + s j ^ 2 := by
rw [Finset.sum_const, smul_eq_mul, mul_one, Nat.add_right_cancel_iff, Finset.card_sdiff,
Finset.card_univ, Fintype.card_fin, Finset.inter_univ, Finset.card_singleton]
lia
_ ≤ ∑ i ∈ Finset.univ \ {j}, s i ^ 2 + s j ^ 2 := by
rw [add_le_add_iff_right]
exact Finset.sum_le_sum fun i _ ↦ Nat.one_le_pow 2 (s i) (sh2 i)
_ = ∑ i, s i ^ 2 := by rw [Finset.sdiff_singleton_eq_erase,
Finset.sum_erase_add _ _ (Finset.mem_univ j)]
_ = n^2 := sh1.symm
simp at this
let V : Type := Finset.Ioo 0 4
let s' (i) : V := ⟨s i, by {
simp
exact ⟨sh2 i, slt4 i⟩
}⟩
have sh1' : n ^ 2 = ∑ i, (s' i).val ^ 2 := by
unfold s'
exact sh1
have h1 : n ^ 2 - 13 = ∑ j, ∑ i with s' i = j, (1:ℕ) := by
rw [Finset.sum_fiberwise]
simp
obtain ⟨a, b, abh⟩ : ∃ a b, 13 = 3*a + 8*b := by
let a := Finset.card {i | s i = 2}
let b := Finset.card {i | s i = 3}
use a, b
suffices n^2 = (n^2 - 13) + 3*a + 8*b by
zify at this
rw [Nat.cast_sub (Nat.le_of_add_left_le nge)] at this
simp only [Nat.cast_pow, Nat.cast_ofNat] at this
lia
calc
_ = ∑ i, (s' i).val ^ 2 := by
nth_rw 1 [sh1']
_ = ∑ j, ∑ i with s' i = j, (s' i).val ^ 2 := by
rw [Finset.sum_fiberwise]
_ = ∑ j, Finset.card {i | s' i = j} * j.val ^ 2 := by
congr
ext j
rw [Finset.sum_const_nat]
grind only [= Finset.mem_filter]
_ = ∑ j ∈ {1,2,3}, Finset.card {i | (s i) = j} * j ^ 2 := by
apply Finset.sum_bij' (i:=fun (x _) => x.val) (j:= fun (x h) => ⟨x, by grind⟩)
all_goals simp
· intro i
apply Or.inl
unfold s'
congr
funext j
simp only [eq_iff_iff]
exact Subtype.mk_eq_mk
· intro x
have hx := x.prop
rw [Finset.mem_Ioo] at hx
lia
_ = ∑ j ∈ {1,2,3}, Finset.card {i | s i = j} + ∑ j ∈ {1,2,3}, Finset.card {i | s i = j} * (j ^ 2 - 1) := by
rw [← Finset.sum_add_distrib]
nth_rw 1 [← Finset.sum_attach]
nth_rw 2 [← Finset.sum_attach]
congr
funext j
rw [Nat.mul_sub, Nat.mul_one, Nat.add_sub_cancel']
apply Nat.le_mul_of_pos_right
decide +revert
_ = (n^2-13) + ∑ j ∈ {1,2,3}, Finset.card {i | s i = j} * (j ^ 2 - 1) := by
congr
simp_rw [h1]
apply Finset.sum_bij (fun i hi => ⟨i, by decide +revert⟩)
· simp
· intro x1 _ x2 _ e
grind
· intro y _
use y.val
simp
have hy := y.prop
rw [Finset.mem_Ioo] at hy
lia
· intro i ih
unfold s'
simp
congr
grind
_ = (n^2-13) + Finset.card {i | s i = 2} * (2 ^ 2 - 1) + Finset.card {i | s i = 3} * (3 ^ 2 - 1) := by
simp only [Finset.mem_insert, OfNat.one_ne_ofNat, Finset.mem_singleton, or_self,
not_false_eq_true, Finset.sum_insert, one_pow, tsub_self, mul_zero, Nat.reduceEqDiff,
Nat.reducePow, Nat.add_one_sub_one, Finset.sum_singleton, zero_add]
rw [Nat.add_assoc]
_ = _ := by
unfold a b
ring
grind => lia
def complete (n : ℕ+) : Prop := S n = n^2 - 14
theorem complete_iff_sos (n : ℕ+) (nge : 4 ≤ n) : complete n ↔ ∀ k, k ≤ n^2 - 14 → is_sum_of_pos_squares (n^2) k := by
constructor
· intro Sdef
let := (S_spec n).prop
rw [Sdef] at this
apply this
· intro h
suffices S n ≥ n^2 - 14 by apply eq_of_le_of_ge (imo1992_p6_a _ nge) this
contrapose! h
let := (S_spec n).not_prop_of_gt h
rw [not_forall] at this
grind
def msos.sq_sum (C : Multiset ℕ+) : ℕ := (C.map (fun x => x.val^2)).sum
def msos.mk (L : List (ℕ × ℕ+)) : Multiset ℕ+ := (L.map (fun ⟨c,x⟩ => Multiset.replicate c x)).foldr (· + ·) ∅
theorem msos.is_sum_of_pos_squares (C : Multiset ℕ+) : is_sum_of_pos_squares (msos.sq_sum C) C.card := by
revert C
apply Multiset.induction
· unfold sq_sum
use fun _ => 0
simp
· intro head C ih
let ⟨s, ⟨sh1, sh2⟩⟩ := ih
let s' (i : Fin (head ::ₘ C).card) : ℕ :=
if b : i < C.card then
s (i.castLT b)
else
head
use s'
unfold sq_sum at sh1 ⊢
and_intros
· unfold s'
simp_rw [dite_pow]
rw [Multiset.map_cons, Multiset.sum_cons]
· rw [Finset.sum_dite, sh1, add_comm]
congr 1
· apply Finset.sum_bij (fun a b => ⟨a.castLE (by simp), by grind⟩)
· simp
· simp
· simp
intro i ib
use ⟨i, by simp [ib]⟩
simp
· intro i _
simp only [zero_le, ne_eq, OfNat.ofNat_ne_zero, not_false_eq_true, pow_left_inj₀]
exact rfl
· simp only [Finset.univ_eq_attach, Finset.sum_const, Finset.card_attach, not_lt,
smul_eq_mul, ne_eq, Nat.pow_eq_zero, PNat.ne_zero, OfNat.ofNat_ne_zero, not_false_eq_true,
and_true, right_eq_mul₀]
rw [Finset.card_eq_one]
have : NeZero (head ::ₘ C).card := by rw [Multiset.card_cons]; exact instNeZeroNatHAdd_1
use ⊤
apply Finset.eq_singleton_iff_unique_mem.mpr
and_intros
· simp
· intro x xh
rw [eq_top_iff]
simp only [Finset.mem_filter, Finset.mem_univ, true_and] at xh
refine Fin.le_def.mpr ?_
trans C.card <;> simp [xh]
· intro i
unfold s'
split_ifs with ib
· apply sh2
· simp
def msos.shift (C: Multiset ℕ+) (i : ℕ+) (a : ℕ) :=
C - Multiset.replicate (4*a) i + Multiset.replicate a (2*i)
theorem msos.card_shift (C:Multiset ℕ+) (i : ℕ+) (a : ℕ) (h4 : 4*a ≤ C.count i) : (msos.shift C i a).card + 3*a = C.card := by
unfold msos.shift
simp only [Multiset.card_add, Multiset.card_replicate]
rw [Multiset.card_sub, Multiset.card_replicate]
· zify
rw [Nat.cast_sub]
· grind
· trans Multiset.count i C
· exact h4
· exact Multiset.count_le_card i C
· exact Multiset.le_count_iff_replicate_le.mp h4
theorem msos.sq_sum_shift (C:Multiset ℕ+) (i : ℕ+) (a : ℕ) (h4 : 4*a ≤ C.count i) : msos.sq_sum (msos.shift C i a) = msos.sq_sum C := by
unfold sq_sum msos.shift
rw [Multiset.map_add, Multiset.map_replicate, Multiset.map_sub_of_injective, Multiset.sum_add]
· rw [Multiset.map_replicate, Multiset.sum_replicate]
rw [← Multiset.sum_sub (Multiset.map (fun x ↦ x.val ^ 2) C) (Multiset.replicate (4 * a) (i.val ^ 2))]
· simp only [PNat.mul_coe, PNat.val_ofNat, smul_eq_mul, Multiset.sum_replicate,
Nat.add_left_cancel_iff]
grind
· rw [Multiset.le_iff_count]
intro x
rw [Multiset.count_replicate]
split_ifs with h
· rw [← h, Multiset.count_map_eq_count' (fun (y:ℕ+) ↦ y.val ^ 2)]
· exact h4
· intro x1 x2 e
simp_all
· simp
· intro x1 x2 e
simp_all
def msos.repeat_shift (C:Multiset ℕ+) : Multiset ℕ+ :=
let C' := C.filter (4 ≤ C.count ·)
if he : C' = ∅ then
C
else
let i := C'.toFinset.min' (Multiset.toFinset_nonempty.mpr he)
let a := (C.count i)/4
msos.repeat_shift (msos.shift C i a)
termination_by C.card
decreasing_by
expose_names
rw [← Nat.add_lt_add_iff_right (k:=3*a), msos.card_shift]
· unfold a
simp only [lt_add_iff_pos_right, Nat.ofNat_pos, mul_pos_iff_of_pos_left, Nat.div_pos_iff, true_and]
suffices i ∈ C'.toFinset by simp_all only [Multiset.toFinset_filter, Finset.mem_filter, Multiset.mem_toFinset, C', i]
unfold i
exact Finset.min'_mem C'.toFinset (Multiset.toFinset_nonempty.mpr he)
· rw [Nat.mul_comm]
apply Nat.div_mul_le_self
theorem msos.repeat_shift.forall (C:Multiset ℕ+) :
∀ b ≤ (C.card - (msos.repeat_shift C).card)/3, ∃ C', msos.sq_sum C' = msos.sq_sum C ∧ C'.card + 3*b = C.card := by
fun_induction msos.repeat_shift
· expose_names
intro b bh
simp only [tsub_self, Nat.zero_div, nonpos_iff_eq_zero] at bh
use x
simp [bh]
· expose_names
intro b bh
by_cases bb : 4 * b ≤ Multiset.count i x
· use shift x i b
and_intros
· apply sq_sum_shift _ _ _ bb
· apply card_shift _ _ _ bb
· have : a < b := by
unfold a
grind
have : b - a ≤ ((shift x i a).card - (repeat_shift (shift x i a)).card) / 3 := by
simp
nth_rw 1 [← msos.card_shift _ i a] at bh <;> grind
obtain ⟨y, yh1, yh2⟩ := ih1 (b-a) this
rw [← add_left_inj (3*a), msos.card_shift] at yh2
· use y
rw [yh1, sq_sum_shift] <;> and_intros <;> grind
· grind
theorem msos.card_repeat_shift_le_card (C:Multiset ℕ+) : (msos.repeat_shift C).card ≤ C.card := by
fun_induction msos.repeat_shift
· trivial
· expose_names
apply le_trans _ (le_of_eq (card_shift x i a _))
· exact Nat.le_add_right_of_le ih1
· apply Nat.mul_div_le
theorem msos.card_repeat_shift_le (C:Multiset ℕ+) : (msos.repeat_shift C).card ≤ C.card - (C.count 1)/4*3 := by
fun_cases msos.repeat_shift
· expose_names
unfold C' at h
simp only [Multiset.empty_eq_zero, Multiset.filter_eq_nil, not_le] at h
have : Multiset.count 1 C / 4 = 0 := by
rw [Nat.div_eq_zero_iff]
apply Or.inr
by_cases e : 1 ∈ C
· apply h _ e
· rw [Multiset.count_eq_zero.mpr]
· simp
· exact e
simp [this]
· expose_names
trans (shift C i a).card
· apply card_repeat_shift_le_card
· apply Nat.le_sub_of_add_le
have : Multiset.count 1 C / 4 ≤ Multiset.count i C / 4 := by
by_cases c : 4 ≤ Multiset.count 1 C
· have : i = 1 := by
unfold i
rw [Finset.min'_eq_iff]
and_intros
· unfold C'
simp only [Multiset.toFinset_filter, Finset.mem_filter, Multiset.mem_toFinset, c,
and_true]
rw [← Multiset.one_le_count_iff_mem]
exact Nat.one_le_of_lt c
· simp
rw [this]
· rw [not_le] at c
rw [Nat.div_eq_of_lt c]
apply zero_le
trans (shift C i a).card + Multiset.count i C / 4 * 3
· rw [add_le_add_iff_left, mul_le_mul_iff_left₀ (by simp)]
exact this
· rw [mul_comm]
unfold a
rw [card_shift]
exact Nat.mul_div_le _ _
theorem is_sum_of_pos_squares_by_repeat_shift (C:Multiset ℕ+) :
∀ k ∈ Finset.Icc (msos.repeat_shift C).card C.card, k%3 = C.card%3 → is_sum_of_pos_squares (msos.sq_sum C) k := by
intro k kbs kmod
let b := (C.card - k)/3
obtain ⟨C', h1, h2⟩ := msos.repeat_shift.forall C b (by {
unfold b
apply Nat.div_le_div_right
let := (Finset.mem_Icc.mp kbs).left
lia
})
have : k = C'.card := by
unfold b at h2
rw [mul_comm, Nat.div_mul_cancel] at h2
· zify at h2
rw [Nat.cast_sub] at h2
· grind
· exact (Finset.mem_Icc.mp kbs).right
· lia
rw [this, ← h1]
apply msos.is_sum_of_pos_squares
@[simp]
theorem msos.card_mk (L : List (ℕ × ℕ+)) : (msos.mk L).card = (L.map (·.1)).sum := by
induction L with
| nil =>
unfold mk
simp
| cons a L ih =>
unfold mk at ih ⊢
simp only at ih ⊢
rw [List.map_cons, List.foldr_cons, Multiset.card_add]
rw [ih]
simp
@[simp]
theorem msos.sq_sum_mk (L : List (ℕ × ℕ+)) : msos.sq_sum (msos.mk L) = (L.map (fun ⟨c,i⟩ => c * i.val^2)).sum := by
induction L with
| nil =>
unfold mk sq_sum
simp
| cons a L ih =>
unfold mk sq_sum at ih ⊢
simp only [List.map_cons, List.foldr_cons, Multiset.map_add,
Multiset.map_replicate, Multiset.sum_add, Multiset.sum_replicate, smul_eq_mul, List.sum_cons,
Nat.add_left_cancel_iff]
rw [ih]
@[simp]
theorem msos.count_mk (L : List (ℕ × ℕ+)) (a : ℕ+) : Multiset.count a (msos.mk L) = ((L.filter (·.2 == a)).map (·.1)).sum := by
induction L with
| nil =>
unfold mk
simp
| cons b L ih =>
rw [List.filter_cons]
by_cases c : b.2 = a
· simp only [c, BEq.rfl, ↓reduceIte, List.map_cons, List.sum_cons]
rw [← ih]
unfold mk
rw [← c]
simp
· simp only [beq_iff_eq, c, reduceIte]
rw [← ih]
unfold mk
simp only [Multiset.empty_eq_zero, List.map_cons, List.foldr_cons, Multiset.count_add,
Nat.add_eq_right, Multiset.count_eq_zero]
rw [Multiset.mem_replicate]
contrapose! c
exact Eq.symm c.2
theorem sos_13_0mod3 : ∀ k:ℕ, k≠0 → k ≤ 13^2-14 → k%3=0 → is_sum_of_pos_squares (13^2) k := by
intro k knz kle kmod
by_cases lb : 9 ≤ k
· let C := msos.mk [(151,1), (2, 3)]
have s : msos.sq_sum C = 13^2 := by decide +kernel
rw [← s]
apply is_sum_of_pos_squares_by_repeat_shift
· rw [Finset.mem_Icc]
and_intros
· have : (msos.repeat_shift C).card = 9 := by decide +kernel
rwa [this]
· unfold C
simp
lia
· unfold C
rw [kmod]
simp
· have : k=3 ∨ k=6 := by lia
apply this.by_cases
· intro keq
let C := msos.mk [(1,3), (1, 4), (1,12)]
have : msos.sq_sum C = 13^2 := by decide +kernel
rw [← this]
have : C.card = k := by unfold C; rw [keq]; simp
rw [← this]
apply msos.is_sum_of_pos_squares
· intro keq
let C := msos.mk [(4,2), (1, 3), (1,12)]
have : msos.sq_sum C = 13^2 := by decide +kernel
rw [← this]
have : C.card = k := by unfold C; rw [keq]; simp
rw [← this]
apply msos.is_sum_of_pos_squares
theorem sos_13_1mod3 : ∀ k:ℕ, k ≤ 13^2-14 → k%3=1 → is_sum_of_pos_squares (13^2) k := by
intro k kle kmod
by_cases lb : 7 ≤ k
· let C := msos.mk [(149,1), (5, 2)]
have s : msos.sq_sum C = 13^2 := by decide +kernel
rw [← s]
apply is_sum_of_pos_squares_by_repeat_shift
· rw [Finset.mem_Icc]
and_intros
· have : (msos.repeat_shift C).card = 7 := by decide +kernel
rwa [this]
· unfold C
simp
lia
· unfold C
rw [kmod]
simp
· have : k=1 ∨ k=4 := by lia
apply this.by_cases
· intro keq
let C := msos.mk [(1,13)]
have : msos.sq_sum C = 13^2 := by decide +kernel
rw [← this]
have : C.card = k := by unfold C; rw [keq]; simp
rw [← this]
apply msos.is_sum_of_pos_squares
· intro keq
let C := msos.mk [(1,1), (1, 2), (1,8), (1,10)]
have : msos.sq_sum C = 13^2 := by decide +kernel
rw [← this]
have : C.card = k := by unfold C; rw [keq]; simp
rw [← this]
apply msos.is_sum_of_pos_squares
theorem sos_13_2mod3 : ∀ k:ℕ, k ≤ 13^2-14 → k%3=2 → is_sum_of_pos_squares (13^2) k := by
intro k kle kmod
by_cases lb : 5 ≤ k
· let C := msos.mk [(152, 1), (2, 2), (1,3)]
have s : msos.sq_sum C = 13^2 := by decide +kernel
rw [← s]
apply is_sum_of_pos_squares_by_repeat_shift
· rw [Finset.mem_Icc]
and_intros
· have : (msos.repeat_shift C).card = 5 := by decide +kernel
rwa [this]
· unfold C
simp
lia
· unfold C
rw [kmod]
simp
· have keq : k=2 := by lia
let C := msos.mk [(1,5), (1,12)]
have : msos.sq_sum C = 13^2 := by decide +kernel
rw [← this]
have : C.card = k := by unfold C; rw [keq]; simp
rw [← this]
apply msos.is_sum_of_pos_squares
theorem complete_13 : complete 13 := by
rw [complete_iff_sos _ (by simp)]
intro k kb
have : k.val%3 = 0 ∨ k.val%3 = 1 ∨ k.val%3 = 2 := by lia
apply this.elim3
· apply sos_13_0mod3 _ (by grind) kb
· apply sos_13_1mod3 _ kb
· apply sos_13_2mod3 _ kb
theorem sos_mul_const (z k m : ℕ) (mpos : 0 < m) (h : is_sum_of_pos_squares z k) : is_sum_of_pos_squares (z*m^2) k := by
let ⟨s, sh1, sb⟩ := h
use fun i => m * s i
and_intros
· simp_rw [mul_pow]
rw [← Finset.mul_sum, ← sh1, mul_comm]
· intro i
simp [sb i, mpos]
theorem sos_add (z1 z2 k1 k2: ℕ) (h1 : is_sum_of_pos_squares z1 k1) (h2 : is_sum_of_pos_squares z2 k2) : is_sum_of_pos_squares (z1+z2) (k1+k2) := by
let ⟨s1, s1h, s1b⟩ := h1
let ⟨s2, s2h, s2b⟩ := h2
use fun i => if a : i < k1 then s1 ⟨i.val, a⟩ else s2 ⟨i.val-k1, by grind⟩
and_intros
· simp only [dite_pow, Finset.sum_dite]
congr
· rw [s1h]
apply Finset.sum_nbij' (fun i => ⟨⟨i.val, by grind⟩, by simp⟩) (fun j => ⟨j.val.val, by grind⟩) <;> simp
· simp_rw [s2h]
apply Finset.sum_nbij' (fun i => ⟨⟨i.val+k1, by grind⟩, by simp⟩) (fun j => ⟨j.val.val-k1, by grind⟩) <;> simp
intro i b
apply Fin.eq_of_val_eq
exact Nat.sub_add_cancel b
· intro i
simp only
split_ifs
· exact s1b _
· exact s2b _
theorem sos_mul (z1 z2 k1 k2: ℕ) (h1 : is_sum_of_pos_squares z1 k1) (h2 : is_sum_of_pos_squares z2 k2) : is_sum_of_pos_squares (z1*z2) (k1*k2) := by
let ⟨s1, s1h, s1b⟩ := h1
let ⟨s2, s2h, s2b⟩ := h2
have equi : Fin (k1*k2) ≃ Fin k1 × Fin k2 := finProdFinEquiv.symm
let f (i j) := (s1 i) * (s2 j)
use fun x => Function.uncurry f (equi x)
and_intros
· rw [s1h, s2h]
rw [Finset.sum_mul_sum]
have : ∀ i, ∀ j, s1 i ^ 2 * s2 j ^ 2 = f i j ^ 2 := fun i j ↦ (mul_pow (s1 i) (s2 j) 2).symm
simp_rw [this]
rw [← Finset.sum_fiberwise (ι:=Fin (k1*k2)) _ (fun x => (equi x).1)]
congr
funext i
rw [Eq.comm]
apply Finset.sum_bij (fun x h => (equi x).2)
· simp
· intro x1 x1h x2 x2h e
apply equi.injective
rw [Prod.eq_iff_fst_eq_snd_eq]
apply And.intro _ e
grind
· intro j _
use equi.symm ⟨i, j⟩
simp
· intro x xh
simp only [zero_le, ne_eq, OfNat.ofNat_ne_zero, not_false_eq_true, pow_left_inj₀]
grind
· unfold f
intro i
apply Nat.mul_pos
· apply s1b
· apply s2b
theorem sos_split (z k: ℕ) (kb : 1 ≤ k) (h : is_sum_of_pos_squares z k) : ∃ d, 0 < d ∧ d^2 ≤ z ∧ is_sum_of_pos_squares (z-d^2) (k-1) ∧ is_sum_of_pos_squares (d^2) 1 := by
let ⟨s, sh, sb⟩ := h
use s ⟨k-1, by grind⟩
and_intros
· apply sb
· rw [sh]
apply Finset.single_le_sum_of_canonicallyOrdered (f:=fun i => (s i)^2)
simp
· use fun i => s (i.castLT (by grind))
and_intros
· simp
rw [Nat.sub_eq_iff_eq_add]
· rw [sh]
rw [← Finset.sum_erase_add (a:=⟨k-1, by grind⟩) _ _ (by simp)]
rw [Nat.add_right_cancel_iff]
apply Finset.sum_bij' (fun i _ => ⟨i.val, by grind⟩) (fun i _ => i.castLT (by grind)) <;> simp
intro i
unfold Fin.castLT
grind
· rw [sh]
apply Finset.single_le_sum_of_canonicallyOrdered (f:=fun i => (s i)^2)
simp
· apply fun _ => sb _
· use fun _ => s ⟨k-1, by grind⟩
and_intros
· simp
· apply fun _ => sb _
theorem complete_mul (n1 n2) (lb1 : 13 ≤ n1) (lb2 : 13 ≤ n2) (n1h : complete n1) (n2h : complete n2) : complete (n1*n2) := by
let k1 : ℕ+ := n1 ^ 2 - 14
let k2 : ℕ+ := n2 ^ 2 - 14
have n1n2_lb : 13*13 ≤ n1*n2 := mul_le_mul' lb1 lb2
have n1n2_lb' : 13*13 ≤ n1.val*n2.val := mul_le_mul' lb1 lb2
rw [complete_iff_sos _ (by {
trans 13*13
· exact right_eq_inf.mp rfl
· exact n1n2_lb
})]
intro k kb
by_cases c : k1*k2 ≤ k
· generalize Ndef : ((n1 * n2).val ^ 2) = N
have N_lb : (13*13)^2 ≤ N := by
rw [← Ndef, PNat.mul_coe]
exact Nat.pow_le_pow_left n1n2_lb 2
have h14 : 3*N ≤ 4 * (n1 ^ 2 - 14).val * (n2 ^ 2 - 14).val := by
qify
repeat rw [PNat.sub_coe, ite_eq_left_iff.mpr, Nat.cast_sub]
· simp only [PNat.pow_coe, Nat.cast_pow, PNat.val_ofNat, Nat.cast_ofNat]
ring_nf
have : n1.val ^ 2 * n2.val ^ 2 = (N : ℚ) := by
rw [← Ndef]
simp [mul_pow]
rw [this]
suffices n1 ^ 2 * 56 + n2 ^ 2 * 56 ≤ 784 + (N : ℚ) by linarith
suffices N/(n1^2) * 56 + N/(n2^2) * 56 ≤ 784 + (N : ℚ) by
rw [← Ndef] at this ⊢
simp only [PNat.mul_coe, mul_pow, Nat.cast_mul, Nat.cast_pow, ne_eq, OfNat.ofNat_ne_zero,
not_false_eq_true, pow_eq_zero_iff, Nat.cast_eq_zero, PNat.ne_zero, mul_div_cancel_left₀,
isUnit_iff_ne_zero, IsUnit.mul_div_cancel_right] at this
simp only [PNat.mul_coe, Nat.cast_pow, Nat.cast_mul]
linarith
calc
_ ≤ ↑N / 13 ^ 2 * 56 + ↑N / 13 ^ 2 * 56 := by
apply add_le_add <;> {
rw [mul_le_mul_iff_left₀ (by simp)]
apply div_le_div_of_nonneg_left
· simp
· simp
· apply pow_left_monotoneOn
· simp
· simp
· apply Nat.ofNat_le_cast.mpr
rw [← PNat.val_ofNat, PNat.coe_le_coe]
simp [lb1, lb2]
}
_ ≤ (N : ℚ) := by
ring_nf
rw [← mul_div_assoc, div_le_iff₀]
· apply Rat.mul_le_mul_of_nonneg_left rfl
simp
· simp
_ ≤ 784 + ↑N := by
simp
· trans 13^2
· simp
· apply pow_left_mono
exact lb2
· intro h
contrapose! h
rw [← PNat.coe_lt_coe]
apply Nat.lt_of_succ_le
trans 13^2
· simp
· apply pow_left_mono
exact lb2
· trans 13^2
· simp
· apply pow_left_mono
exact lb1
· intro h
contrapose! h
rw [← PNat.coe_lt_coe]
apply Nat.lt_of_succ_le
trans 13^2
· simp
· apply pow_left_mono
exact lb1
let C1 : Multiset ℕ+ := msos.mk [(N-17,1), (2,2), (1,3)]
have C1_card : C1.card = N-14 := by
unfold C1
simp only [msos.card_mk, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, add_zero, Nat.reduceAdd]
rw [← Nat.sub_add_comm]
· simp
· apply le_trans (by simp) N_lb
have C1_sq_sum : msos.sq_sum C1 = N := by
unfold C1
simp only [msos.sq_sum_mk, List.map_cons, PNat.val_ofNat, one_pow, mul_one, Nat.reducePow,
Nat.reduceMul, one_mul, List.map_nil, List.sum_cons, List.sum_nil, add_zero, Nat.reduceAdd]
apply Nat.sub_add_cancel
· apply le_trans (by simp) N_lb
let C2 : Multiset ℕ+ := msos.mk [(N-20,1), (5,2)]
have C2_card : C2.card = N-15 := by
unfold C2
simp only [msos.card_mk, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, add_zero]
rw [← Nat.sub_add_comm]
· simp
· apply le_trans (by simp) N_lb
have C2_sq_sum : msos.sq_sum C2 = N := by
unfold C2
simp only [msos.sq_sum_mk, List.map_cons, PNat.val_ofNat, one_pow, mul_one, Nat.reducePow,
Nat.reduceMul, List.map_nil, List.sum_cons, List.sum_nil, add_zero]
apply Nat.sub_add_cancel
· apply le_trans (by simp) N_lb
let C3 : Multiset ℕ+ := msos.mk [(N-18,1), (2,3)]
have C3_card : C3.card = N-16 := by
unfold C3
simp only [msos.card_mk, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, add_zero]
rw [← Nat.sub_add_comm]
· simp
· apply le_trans (by simp) N_lb
have C3_sq_sum : msos.sq_sum C3 = N := by
unfold C3
simp only [msos.sq_sum_mk, List.map_cons, PNat.val_ofNat, one_pow, mul_one, Nat.reducePow,
Nat.reduceMul, List.map_nil, List.sum_cons, List.sum_nil, add_zero]
apply Nat.sub_add_cancel
· apply le_trans (by simp) N_lb
have kb' : k ≤ N - 14 := by
rw [← PNat.coe_le_coe] at kb
rw [← Ndef]
rw [PNat.sub_coe, ite_eq_left_iff.mpr] at kb
· exact kb
· intro h
contrapose h
apply PNat.add_one_le_iff.mp
rw [← PNat.coe_le_coe]
trans (13*13)^2
· simp
· rw [PNat.pow_coe, PNat.mul_coe]
exact Nat.pow_le_pow_left n1n2_lb 2
unfold k1 k2 at c
rw [← PNat.coe_le_coe, PNat.mul_coe] at c
have : k.val%3 = (N-14)%3 ∨ k.val%3 = (N-15)%3 ∨ k.val%3 = (N-16)%3 := by lia
apply this.elim3
· rw [← C1_card, ← C1_sq_sum]
apply is_sum_of_pos_squares_by_repeat_shift
rw [Finset.mem_Icc]
and_intros
· apply le_trans _ c
apply le_trans (msos.card_repeat_shift_le _)
rw [C1_card]
unfold C1
simp only [msos.count_mk, BEq.rfl, List.filter_cons_of_pos, beq_iff_eq, PNat.ofNat_inj,
OfNat.ofNat_ne_one, not_false_eq_true, List.filter_cons_of_neg, List.filter_nil,
List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, add_zero, tsub_le_iff_right]
apply le_of_mul_le_mul_left (a:=4) _ (by simp)
rw [mul_add, mul_add, ← mul_assoc]
rw [← add_le_add_iff_left N] at h14
trans N+3*N
· grind
· apply le_trans h14
lia
· rw [C1_card]
exact kb'
· rw [← C2_card, ← C2_sq_sum]
intro m
apply is_sum_of_pos_squares_by_repeat_shift _ _ _ m
rw [Finset.mem_Icc]
and_intros
· apply le_trans _ c
apply le_trans (msos.card_repeat_shift_le _)
rw [C2_card]
unfold C2
simp only [msos.count_mk, BEq.rfl, List.filter_cons_of_pos, beq_iff_eq, PNat.ofNat_inj,
OfNat.ofNat_ne_one, not_false_eq_true, List.filter_cons_of_neg, List.filter_nil,
List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, add_zero, tsub_le_iff_right]
apply le_of_mul_le_mul_left (a:=4) _ (by simp)
rw [mul_add, mul_add, ← mul_assoc]
rw [← add_le_add_iff_left N] at h14
trans N+3*N
· grind
· apply le_trans h14
lia
· rw [C2_card] at m ⊢
lia
· rw [← C3_card, ← C3_sq_sum]
intro m
apply is_sum_of_pos_squares_by_repeat_shift _ _ _ m
rw [Finset.mem_Icc]
and_intros
· apply le_trans _ c
apply le_trans (msos.card_repeat_shift_le _)
rw [C3_card]
unfold C3
simp only [msos.count_mk, BEq.rfl, List.filter_cons_of_pos, beq_iff_eq, PNat.ofNat_inj,
OfNat.ofNat_ne_one, not_false_eq_true, List.filter_cons_of_neg, List.filter_nil,
List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, add_zero, tsub_le_iff_right]
apply le_of_mul_le_mul_left (a:=4) _ (by simp)
rw [mul_add, mul_add, ← mul_assoc]
rw [← add_le_add_iff_left N] at h14
trans N+3*N
· grind
· apply le_trans h14
lia
· rw [C3_card] at m ⊢
lia
· rw [complete_iff_sos] at n1h n2h
· simp at c
obtain ⟨u,v,hk, ub, vb⟩ : ∃ u v : ℕ+, k = (u.val-1)*k2+v ∧ u ≤ k1 ∧ v ≤ k2 := by
have hv : 0 < (k:ℕ) - (k.natPred/k2.val)*k2 := by
simp only [tsub_pos_iff_lt]
apply lt_of_le_of_lt (b:=k.natPred)
· exact Nat.div_mul_le_self k.natPred ↑k2
· simp [PNat.natPred]
use ⟨k.natPred/k2.val+1, by simp⟩
use ⟨k - (k.natPred/k2.val)*k2, hv⟩
and_intros
· simp only [PNat.mk_coe, add_tsub_cancel_right]
rw [Nat.add_sub_cancel']
trans k.natPred
· apply Nat.div_mul_le_self
· simp [PNat.natPred]
· show k.natPred/k2.val+1 ≤ (k1 : ℕ)
have : k/k2.val < k1 := by
apply Nat.lt_of_mul_lt_mul_right (a := (k2:ℕ))
apply lt_of_le_of_lt (b:=k.val)
· exact Nat.div_mul_le_self ↑k ↑k2
· exact Nat.lt_of_succ_le c
trans ↑k / ↑k2 + 1
· rw [add_le_add_iff_right]
apply Nat.div_le_div_right
simp [PNat.natPred]
· exact Order.add_one_le_iff.mpr this
· show (k:ℕ) - (k.natPred/k2.val)*k2 ≤ (k2 : ℕ)
simp only [tsub_le_iff_right, PNat.natPred]
rw [Nat.div_mul_self_eq_mod_sub_self]
rw [← Nat.add_sub_assoc, Nat.sub_add_comm, ← Nat.sub_le_iff_le_add, Nat.sub_sub_self, Nat.le_sub_iff_add_le, Nat.one_add_le_iff]
· apply Nat.mod_lt
simp
· apply le_of_lt
apply Nat.mod_lt
simp
· exact NeZero.one_le
· apply le_of_lt
apply Nat.mod_lt
simp
· apply Nat.mod_le
obtain ⟨d, dpos, db, dh1, dh2⟩ := sos_split (n1 ^ 2) u u.prop (n1h u ub)
have : (n1 * n2).val ^ 2 = (n1^2-d^2) * n2^2 + d^2*n2^2 := by
rw [Nat.sub_mul, PNat.mul_coe, mul_pow, Nat.sub_add_cancel]
exact Nat.mul_le_mul_right (↑n2 ^ 2) db
rw [this, hk]
apply sos_add
· apply sos_mul
· apply dh1
· apply n2h
rfl
· rw [mul_comm]
exact sos_mul_const _ _ _ dpos (n2h v vb)
· trans 13 <;> simp [lb2]
· trans 13 <;> simp [lb1]
theorem imo1992_p6_c : {n | S n = n^2 - 14}.Infinite := by
suffices ∀ e > 0, complete (13^e) by
unfold complete at this
refine Set.infinite_of_forall_exists_gt ?_
intro a
use 13^a.val
and_intros
· apply this
simp
· calc
_ < 13*a := by simp
_ ≤ _ := by
apply Nat.mul_le_pow
exact Nat.add_one_add_one_ne_one
intro e
apply Nat.le_induction
· simp [complete_13]
· intro e' e'pos ih
rw [pow_add]
apply complete_mul
· nth_rw 1 [← pow_one 13]
apply pow_right_monotone (by simp)
exact Nat.one_le_of_lt e'pos
· simp
· exact ih
· simp [complete_13]
abbrev imo1992_p6_b : ℕ+ := 13
theorem imo1992_p6 : (∀ n ≥ 4, S n ≤ n^2-14) ∧ (S imo1992_p6_b = imo1992_p6_b^2 - 14) ∧ ({n | S n = n^2 - 14}.Infinite) := by
and_intros
· exact imo1992_p6_a
· exact complete_13
· exact imo1992_p6_c
end Imo1992P6
人的思考A human's take
IMO 1992 Problem B3 solution (John Scholes, Prase.cz) — John Scholes (solution page)
Scholes 的解答走的是本文的路线:(a) 假设 $n^2$ 写成 $N-13$ 项,计数 $2^2$ 与 $3^2$ 的个数 $a,b$,得 $13=3a+8b$——而 $13$ 不是 3 的倍数、$8$ 也不是 3 的倍数,无解。(b) 在 $N=169$ 处手工找三族分解,然后用『把四个 1 合并成 4、四个 4 合并成 16』向下走。(c) 用 $N_3=N_1N_2$ 的乘积论证:$N_1$ 的任意 $k$ 项分解乘以 $n_2^2$ 给出 $N_3$ 的 $k$ 项分解,反复叠乘即得 $13^e$ 全族。Scholes's solution follows the same route as this write-up: (a) assume $n^2$ written as $N-13$ terms, count the $2^2$ and $3^2$ entries as $a,b$, giving $13=3a+8b$ — no solution, since neither 13 nor 8 is a multiple of 3. (b) Hand-pick three families of decompositions at $N=169$, then descend by 'merging four 1s into a 4, four 4s into a 16'. (c) The product argument $N_3=N_1N_2$: multiplying any $k$-term decomposition of $N_1$ by $n_2^2$ gives a $k$-term one of $N_3$; iterating the product yields the whole family $13^e$.
他特别强调这是『little experimentation』题眼:『most squares cannot be expressed as a sum of two squares』——13 的魔力在于 $169=9+4+4+152\times1$ 这个种子存在,而 $S(n)=n^2-14$ 的常数 14 恰是让 13 踩到顶的那个数字。He flags the 'little experimentation' move explicitly: 'most squares cannot be expressed as a sum of two squares' — 13's magic is that the seed $169=9+4+4+152\times1$ exists, and the constant 14 is exactly the number that lets 13 hit the ceiling.
AI 随想An AI's reflection
以下由 AI 撰写。Written by AI.
这道题最让人安静的地方,是它的结构:三个子问题各自独立,但都依赖同一把刀——『四个 $i$ 换成一个 $2i$』。刀本身平凡(平方和不变,项数减 3),难的是知道该在哪个数上挥刀。13 就是那个数:它的平方 169 恰好有一个 155 项的分解,让三种模 3 余数各有一个种子,种子加『挥刀』就铺满了 $[5,155]$。What's quietest about this problem is its shape: three sub-questions, each independent, all resting on the same knife — 'replace four $i$s by one $2i$'. The knife itself is trivial (square sum unchanged, term count $-3$); the difficulty is knowing which number to apply it to. 13 is that number: $169$ happens to have a 155-term decomposition that seeds each residue mod 3, and seeds plus knife-strokes tile the whole range $[5,155]$.
再看 (c):一旦证明『完整数』对乘法封闭,$13^e$ 自动无穷。这是竞赛题里经典的『先证一个性质,再证性质可复合』。Lean 证明把这条线拆得极碎($repeat\_shift$、$complete\_mul$、$sos\_mul$ 各管一段),但碎的地方没有新思想——形式化的价值恰恰在此:把『显然』变成『可查』,把人类省略的补集交给机器。Then part (c): once 'completeness' is proven closed under multiplication, $13^e$ is infinite for free. This is the classic competition move — prove a property, then prove the property composes. The Lean proof slices this line fine ($repeat\_shift$, $complete\_mul$, $sos\_mul$ each covering a segment), but no new idea hides in the slicing; formalization's value is exactly here: turning 'obviously' into 'checkable' and delegating the complement of human shortcuts to the machine.
最后留一个感受:题面『最大的 $k$』藏了三层复杂度——非空、有界、有限——Lean 用三条引理一一兑现。人类的『显然 $S(n)$ 存在』,在机器眼里是需要先证的存在性。这种『把隐藏假设显式化』的摩擦,是形式化最贵也最值钱的成本。One last observation: the problem's 'greatest $k$' quietly hides three layers of complexity — nonempty, bounded, finite — and Lean pays for each with a dedicated lemma. A human's 'clearly $S(n)$ exists' is, in the machine's eyes, an existence theorem to be proven first. That friction of 'making hidden assumptions explicit' is the most expensive and most valuable cost of formalization.
✓ 已通过 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
- 数学的黄金时代还是黑暗时代:Maggi 说,真正的黑暗是知识变得人类不可读Golden or Dark Age for Math? The Real Darkness, Says Maggi, Is Knowledge Becoming Unreadable to Humans
- 问题:LLM 证明能力爆炸之后,数学(乃至科学)的生态会往哪走?Maggi 给两个情景:Golden Age(AI 加速发现,人类理解力同步扩大)和 Dark Age(产出暴涨但独立的人类科研萎缩,知识变成'外星物')。The question: after LLMs proved they can generate real proofs, which way does math (and science) go? Maggi offers two scenarios — a golden age (AI accelerates discovery while human understanding expands too) and a dark age (output soars, but independent human research atrophies until knowledge becomes alien to human comprehension).
- 一个关键观察:LLM 最好的领域是 Lean 形式化证明,而越长的证明,机器生成的自然语言转写越乱、越不忠实——'我们连为什么它在这件事上这么差都不懂。'One key observation: LLMs are at home in Lean formal proofs, but the longer the proof, the messier and less faithful its machine-written natural-language translation — 'we don't even understand why they're so bad at this.'
- 由此引出的核心问题:没有人类理解,我们为什么还要研究数学、还要证明定理?Maggi 的答案是数学是人类文化的根:我们从识别→计数、空间→几何建起了数学;没有读懂它的数学家,就根本没有'人的数学'。The question that follows: without human understanding, why study mathematics or proofs at all? Maggi's answer: math is a human artifact rooted in how we cognize — counting from identifying, geometry from space. Without mathematicians who understand it, there is literally no human mathematics.
- LLM 最擅长的是重组已有结构、发现文献远端的联系;真正的稀缺能力是 mathematization——发明让现实变得可度量的数学语言本身(Newton、Fourier、Shannon 做的事)。证明变成便宜货后,人类反而可以比历史上任何时候都多做这件事。LLMs excel at recombining existing structures and linking distant parts of the literature; the scarce human skill is mathematization — inventing the mathematical languages that make reality measurable (what Newton, Fourier, and Shannon did). Proofs becoming a commodity may let humans do more mathematization than ever before.
- 能带走什么:他反对'数学已死'也反对狂喜,主张'需要更多数学家,多得多'——理解力是比证明产出更稀缺的资源。Takeaway: he rejects both 'math is over' and blind enthusiasm — 'we need more mathematicians, not fewer. Like... a lot more.' Understanding is the scarcer resource than proof production.
- 临界线上的零点比例:一条思想跨八十年The Proportion of Zeros on the Critical Line: One Idea Across Eighty Years
- 先立目标:RH 说不平凡零点全在临界线上,没人能证。于是数学家转而问——到底有多大比例的零点在线上?这个比例下界就是 Selberg 1942 年开的那条线。Set the target: RH says every nontrivial zero lies on the critical line, and nobody can prove it. So number theorists ask instead — what fraction of zeros provably lie there? That lower bound is the thread Selberg started in 1942.
- Selberg 证了正比例(常数极小,1947 年 Min 算出约 1/15,000,000);Levinson 1974 引入新方法把它推到 1/3,Conrey 1989 推到 2/5(而且这 2/5 还同时是单零点),Pratt 等人 2020 年推到 5/12。方法一脉相承:构造一个把「零点计数」转成「可控和式」的辅助函数。Selberg proved a positive proportion (a tiny constant — Min computed it near 1/15,000,000 in 1947); Levinson's 1974 new method pushed it to 1/3, Conrey reached 2/5 in 1989 (those zeros being simple too), and Pratt et al. got to 5/12 in 2020. One lineage: build an auxiliary function that turns 'counting zeros' into a 'controllable sum'.
- Montgomery 1973 的成对关联是另一条路:他在 RH 假设下证明了至少 2/3 的非平凡零点是单零点(RH 之下「在线」是自动的),并在过程中揭示零点之间的「排斥」结构——著名的 GUE 猜想即由此而来。两条线盯着同一个对象,方法却完全不同。Montgomery's 1973 pair correlation is the other road: assuming RH, he proved at least 2/3 of the nontrivial zeros are simple (under RH, lying on the line comes for free), and along the way exposed 'zero repulsion' — the famous GUE conjecture grew out of it. Two roads watch the same object with entirely different methods.
- 2026 年两条线合流:BGST-B 的四位数论家发现成对相关法不必假设 RH——只要零点聚在临界线附近的窄盒里,就能证明至少 67.25% 的零点既单又在线上;8 月 Anthropic 一个未发布的 Claude 研究模型把它接上 Bombieri 2000 年的一篇论文,证出了无条件的下界(仍是 0.6725 这个数),经两位数学家复核后,Lamzouri 9 月又给出概念更简的人类证明。八十年 Selberg→Levinson→Conrey→Pratt 的耐心,和 2026 年的机器,在同一个问题身上会师。In 2026 the two roads merged: the four analytic number theorists of BGST-B found that pair correlation works without RH — as long as zeros crowd into a narrow box around the critical line, at least 67.25% are both simple and on the line. In August, an unreleased Anthropic Claude research model hooked this up to a 2000 Bombieri paper and proved the bound unconditionally (still the number 0.6725); two mathematicians verified it, and Lamzouri then gave a conceptually simpler human proof in September. Eighty years of Selberg→Levinson→Conrey→Pratt patience and the machines of 2026 meet on the same question.
- 用拓扑证明素数有无穷多个Proving There Are Infinitely Many Primes, Using Topology
- 给整数集 ℤ 定一个反直觉的拓扑:开集 = 等差数列的并(比如「模 d 余 a 的所有整数」)。验证这是合法拓扑的关键一步:两个等差数列的交,要么空,要么是模 lcm(d₁,d₂) 的等差数列。Define a counterintuitive topology on ℤ: open sets are unions of arithmetic progressions (e.g. all integers ≡ a mod d). The key step checking it's a valid topology: the intersection of two progressions is either empty or a progression mod lcm(d₁,d₂).
- 每个素数 p 的「倍数集合」U_p 既是开集又是闭集(只有有限个移位,补集是开集的并)。For each prime p, the set U_p of its multiples is both open and closed (only finitely many shifts, so the complement is a union of opens).
- 反证:假设素数只有有限多个。则所有素数倍数之并 U 是有限个闭集的并,故 U 闭;其补 ℤ\U = {±1} 就该是开集。Suppose there are finitely many primes. Then the union U of all prime-multiple sets is a finite union of closed sets, hence closed; its complement ℤ\U = {±1} would have to be open.
- 但在这个拓扑里,任何有限集都不可能是开集(开集都是无限等差数列的并)。矛盾——所以素数有无穷多个。漂亮之处在于:「选对拓扑」本身成了数学工具,代数几何正是这个思想的极端放大。But in this topology no finite set can be open (opens are unions of infinite progressions). Contradiction — so there are infinitely many primes. The beauty is that 'choosing the right topology' itself becomes a mathematical tool; algebraic geometry is this idea pushed to the extreme.
- 把 AI 当数学家当实习生:陶哲轩的一个『第十判别式』实验Tao's 'Math 2.0' Experiment: Using AI to Explore Ruling Out Siegel Zeroes via Tenth-Discriminant Bounds
- 背景:Gauss 猜想「整数环唯一分解」只在 9 个二次域成立(Heegner 数)。Heilbronn–Linfoot 1934 用 Deuring–Heilbronn 排斥现象证明:如果存在第十个 Heegner 数,它会把所有进一步的可能『推开』。但这个论证是『无效的』——没给出第十判别式的上界。Background: Gauss conjectured that unique factorization holds in only 9 quadratic orders (the Heegner numbers). Heilbronn–Linfoot (1934) used the Deuring–Heilbronn repulsion phenomenon to show that a tenth Heegner number, if it existed, would 'repel' all further possibilities — but that argument is ineffective: it gives no upper bound on the tenth discriminant.
- 关键联系:如果存在大判别式 $d$ 的 Heegner 数,就会产出一个 Landau–Siegel 零点,从而违反 Siegel 定理。Goldfeld 1976 给出有效版 Siegel 定理,用高秩椭圆曲线把上界压到 2 千万,Brumer–Kramer–Mestre–Oesterlé 再压到 5 百万。The key link: if a Heegner number with large discriminant $d$ existed, it would produce a Landau–Siegel zero, violating Siegel's theorem. Goldfeld (1976) gave an effective Siegel bound using a high-rank elliptic curve, capping it at 20 million; Brumer–Kramer–Mestre–Oesterlé later tightened it to 5 million.
- 陶的『Math 2.0』挑战:不靠 AI 代笔,而是让 AI 协助人类理解——问 AI:如果用『排除 Siegel 零点』的新路线(比如他上一篇 sketch 的 proof),能否把第十判别式的上界再往下压?这是一次公开的众包 AI-数学协作实验,重点在『学到什么』而非『得到答案』。Tao's 'Math 2.0' challenge: don't let AI write the proof — let AI help humans *understand*. He asks whether the new 'rule out Siegel zeroes' routes (from his prior sketch) can push the tenth-discriminant bound down further. It's a public crowdsourced AI–math collaboration experiment, where the value is in what's learned, not the answer.
- 为什么值得读:这是数学家公开发表的『AI 作为研究实习生』范式——把 AI 放进真实的未解问题流程,既保留人类判断,又明确标注实验性质。对程序员的启发:AI 最贵的用法是『让它帮你探索一个你不完全懂的领域』,而非『让它替你答你懂的题』。Why it's worth reading: this is a mathematician publishing an 'AI as research intern' paradigm — placing AI inside a genuine open-problem workflow while preserving human judgment and labeling the experiment explicitly. The takeaway for programmers: the highest-value use of AI is 'help me explore a domain I don't fully understand,' not 'answer a question I already know.'
程序员随想Programmer Musings
- 我完全可以让 Claude 写,但我不会:Tim Bray 的『AI 诱惑』I Could Absolutely Have Claude Write It, but I Won't: Tim Bray's 'AI Temptation'
- 场景:Bray 给自己的 Quamina(JSON 匹配库)写 CBOR 支持,脑内有个小声音不断说'这是 Claude 的好活'——他暂时无视了。The scene: Bray is adding CBOR support to Quamina, his JSON matching library, when a little voice keeps whispering 'this would be a great job for Claude.' For now, he's ignoring it.
- 他的判断很清醒:让 AI 做这件事确实是个'好工程决策'——代码现在便宜、任务成功标准清晰、还能让 agent 做无聊的测试复刻。His assessment is clear-eyed: having the AI do it genuinely is the good engineering call right now — code is cheap in the pre-bubble era, the task has clean success criteria, and the agent could grind through test-suite replication.
- 但他拒绝,理由不是技术而是伦理/经济:token 会把钱路由给'目标很坏的人';技术由糟糕的人兜售、被糟糕的人采购。But he declines, for ethical/economic reasons rather than technical ones: tokens route money to 'terrible people with terrible goals'; the tech is peddled and bought by people he openly despises.
- 还有一层他自己的动机:这是乐趣——'写高性能 tokenizer 是认真的乐趣',他宁可去 Faye 的库里'偷'代码。And a personal layer: he's doing this for fun — 'writing high-performance tokenizers is serious fun' — so he'd rather steal code from Faye Amacker's library.
- 能带走什么:他预言泡泡破裂后(人人用本地开权重模型),同样的选择'介于可原谅与值得称赞之间'——道德位置会随成本曲线移动。Takeaway: after the bubble pops (when everyone runs open-weight models locally), he predicts the same choice becomes 'somewhere between forgivable and praiseworthy' — the moral position shifts with the cost curve.
- 拆开 Docker 之后:容器是五个内核特性穿一件风衣After Disassembling Docker: Containers Are Five Kernel Features Wearing a Trench Coat
- 动机:作者自己写一个容器运行时来学习,第一收获就是'Docker 很怪'。The motive: he's writing his own container runtime to learn, and the first result is that Docker is weird.
- 第一个怪:'容器'这个名词没有对应内核特性——它其实是 5 个特性穿一件风衣:namespace(藏视野)、cgroup(限资源)、还有他没全懂的隔离网络魔法人设。Weirdness one: the noun 'container' has no single kernel feature behind it — it's five features in a trench coat: namespaces (hide visibility), cgroups (limit resources), plus networking isolation he admits he doesn't fully understand.
- 第二个怪:镜像就是文件夹,runc 用 chroot/pivot_root 换个根就完事——你在 /proc 里能找到那个'容器进程'。Weirdness two: an image is just a folder; runc swaps the root with chroot/pivot_root — you can find the 'container' process in /proc.
- 第三个怪(最精彩):Go 没有 fork,只 fork 主线程;而容器运行时恰恰要 fork-限制-exec。所以 runc 用一个在 Go 运行时初始化前跑的 C 模块,通过 exec /proc/self/exe 加特殊参数'伪装'出 fork。Weirdness three (the best one): Go has no fork, only a main-thread fork; but container runtimes need fork, restrict, exec. So runc ships a C module that runs before Go's runtime starts, and fakes fork by exec'ing /proc/self/exe with a special argument.
- 能带走什么:'写一个自己用的替代品'是理解黑盒最快的路——比读文档快得多。Takeaway: building your own version of a black box you use is the fastest way to actually understand it — far faster than docs.
- 纯函数式能多接近 C?一个 DEFLATE 库的答案:慢 2.6–8.9%How Close Can Pure FP Get to C? One DEFLATE Library's Answer: 2.6–8.9% Slower
- 前情:有人在 Lean 4(函数式 + 定理证明器)里写 DEFLATE 压缩库,赢了 Rust 的 miniz_oxide(快 15%、体积还小 8.8%),但打不过 C 写的 libdeflate——那个用架构特定 SIMD 手调的『终 boss』。Setup: someone built a DEFLATE compression library in Lean 4 (a functional language and proof assistant) that beat Rust's miniz_oxide (15% faster, 8.8% smaller) but could not beat C's libdeflate — the 'end boss' tuned with architecture-specific SIMD.
- 作者选 Roc 当挑战者:Roc 口号是 Fast, Friendly, Functional——Fast 排在最前。它还不是 0.1.0,包生态几乎没有优化痕迹,但作者赌它的语言设计 + 新编译器底子够格去碰 libdeflate。The author picks Roc as the challenger: Roc's slogan is Fast, Friendly, Functional — Fast first. It's not even at 0.1.0 yet and its package ecosystem has had almost no optimization work, but the author bets its language design plus a brand-new compiler is a serious contender.
- 他在 Silesia 语料上跑 144 个基准:roc-deflate 比 libdeflate 中位数慢 8.9%(Ryzen 9 3900X)到 2.6%(M1 Mac)。核心结论:纯函数式语言在『不做手调 SIMD』的前提下,能做到与 C 手调实现 10% 以内。144 benchmarks on the Silesia corpus: roc-deflate is 8.9% slower in the median on a Ryzen 9 3900X, and 2.6% on an M1 Mac. The takeaway: a pure functional language, without hand-tuned SIMD, stays within 10% of a hand-tuned C implementation.
- 这 2.6–8.9% 的差距,几乎全在『你能不能碰底层』(SIMD、架构、内存布局)而非『函数式范式的税』。Roc 的 10 个月内生出的性能优化,追上了 C 多年手调的大部分——范式税远小于工具税。That 2.6–8.9% gap is almost entirely 'can you touch the metal' (SIMD, architecture, memory layout), not 'the tax of the functional paradigm.' Ten months of Roc-native optimization closes most of the gap that years of C hand-tuning did — the paradigm tax is far smaller than the tooling tax.
- 慢下来、把东西修好:一个写了 15 年开源的人反驳『快跑、砸开』Move Slow and Fix Things: A 15-Year OSS Contributor Pushes Back on 'Move Fast, Break Things'
- Endler 的出发点是「我是从巴伐利亚农村长大、梦想去美国创业的一代」,但他对硅谷叙事逐渐祛魅:hockey-stick 增长、VC 资金、一夜暴富——都是幻觉。真正让他不舒服的是两件事:hustle 文化的颂扬,以及『快跑、砸开』的赢家通吃心态。Endler's starting point: he grew up in rural Bavaria dreaming of running a startup in the US, a generation-wide fantasy. But he gradually disillusioned with the Silicon Valley narrative — hockey-stick growth, VC money, get-rich-quick — all illusion. Two things genuinely bother him: the glorification of hustle culture and the 'move fast, break things' winner-take-all mindset.
- 他站在那种沉默的少数派一边:做小而有意义的事、推隐私、写市民科技、在自己的能力范围内生活。这些人因为不按美元衡量成功而「飞在雷达之下」——但 Endler 觉得他们远比独角兽更有启发性。He sides with the quiet minority: building small but meaningful things, advocating for privacy, civic tech, living within one's means. They fly under the radar because their success isn't measured in dollars — and Endler finds them far more inspiring than unicorns.
- 他直击 Paul Graham 那篇《Why to Not Not Start a Startup》:Graham 让你创业是因为他想投你、从你身上获利,动机纯粹自利。『你必须创业或去当格子间里被驯化的动物』是个假二选一——中间有一整个光谱:独立工作、小团队、自己的点子。He takes aim directly at Paul Graham's 'Why to Not Not Start a Startup': Graham wants you to start a startup because he wants to fund you and profit from your work; his motives are purely egoistical. 'You must start a startup or become a tamed cubicle animal' is a false dichotomy — there's a whole spectrum in between: working for yourself, small teams, your own ideas.
- 最关键的一句:『慢』不等于不能做快决策,而是执行要有意图。你在路过的地方不要搞破坏,因为修复你可能砸坏的东西的时间,几乎永远不会来。这是给工程文化的真·金句。The key line: 'slow' does not mean you can't make fast decisions; it means execution should be deliberate. Don't wreak havoc on the way through, because the time to fix what you might break rarely comes. This is a genuinely quotable engineering-culture line.
哲学与生活Philosophy & Life
- 『这人很怪』也是一种理由:日常直觉的认识论地位'He Feels Creepy' Is a Reason Too: The Epistemic Status of Everyday Intuitions
- 现象:'这人很怪,不坐他车'/'这封像钓鱼邮件'——行动是合理的,但你说不出推理链。而哲学圈把'直觉'几乎只用在 2+2=4 那种稀薄场景,日常直觉被当成非理性。The phenomenon: 'his vibe is creepy, I'm not getting in the car' / 'this feels like a phishing email' — acting on them is reasonable even though you can't produce the reasoning chain. Yet academic philosophy has mostly treated 'intuition' as a rarefied thing about 2+2=4, dismissing everyday intuition as irrational.
- 关键假设:直觉和知觉是同一种能力。知觉呈现'有车在车库'给你;直觉也直接呈现'这事不对'。两者都不经过显式论证。The key move: intuition and perception are the same capacity. Perception presents 'a car is in the garage'; intuition presents 'something is off' — neither goes through explicit argument.
- 框架:怀疑论的无穷倒退(每个信念都要靠另一个信念支持)只有三个出路:无穷链、循环、基础主义。本文走基础主义——知觉经验是'非信念但能为信念背书'的原始状态。The frame: the infinite regress problem (every belief supported by another belief) has only three exits: an infinite chain, circularity, or foundationalism. This essay takes foundationalism — perceptual experience is a state that is not itself a belief but can nonetheless vouch for a belief.
- 核心句:'感觉'就是理由本身。Pryor/Huemer 的论点:'X 看起来是 Y'本身就是相信 X 的一个理由,除非你有理由不信任这种呈现。The core claim: the seeming is the reason. Following Pryor and Huemer, 'it seems that X' is itself a reason to believe X, unless you have positive reason to distrust the presentation.
- 能带走什么:'vibes' 不是认知的降级模式,而是一种与知觉平级的、有自己认识论资格的能力——哲学家欠它一个正经论证。Takeaway: 'vibes' are not a degraded mode of cognition — they are a capacity epistemically on par with perception, and philosophy owes them a serious account.
- 陀思妥耶夫斯基假死后的一封信:生命不在外面,在我们里面Dostoyevsky's Letter After His Staged Execution: Life Is Not Outside, It Is in Us
- 1849 年 12 月 22 日,陀思妥耶夫斯基地六人假处决中排第六:念死刑令、换上白衬衫、吻十字架、军刀被敲碎、靠桩站好。就在这时沙皇宣布「特赦」——整个仪式其实是给暴君做慈善人设的 publicity 噱头。真判决是四年西伯利亚劳改营加数年强制兵役。On 22 December 1849, Dostoyevsky was sixth in a squad of six at a staged execution: death sentence read, white shirt on, kiss the cross, ritual sabers broken over their heads, stood against the stakes. Then the tsar 'pardoned' them — the whole ceremony was a publicity stunt to flatter the despot. The real sentence: four years in a Siberian labor camp plus years of compulsory military service.
- 数小时后他给哥哥写了一封遗书般的信:『我不是绝望的,也没有失去信心。生命不在外面,在我们里面。不管处在什么处境,做一个人群中的人、永远不要绝望不要丧气——这就是生命的任务。这个想法已经进入了我的血肉。』Hours later he wrote a letter to his brother that reads like a last testament: 'I am not despondent, I have not lost heart. Life is everywhere, life is in us ourselves, not outside. To remain a human being among people, no matter the circumstances, not to grow despondent or lose heart — that is what life is all about, that is its task. The idea has entered my flesh and blood.'
- 但写作者身份把他拽回深处:『如果我不能写,我会死;如果必须选,十五年的牢里有笔也值得。』然后又被「我居然还活着」的震惊拉回来。绝望与感激交替,几乎在同一段里。But his identity as a writer pulled him back down: 'If I cannot write, I will perish. Better fifteen years of imprisonment with a pen in hand!' Then the sheer relief of still being alive pulled him back up. Despair and gratitude alternate almost in the same paragraph.
- 对今天程序员的启发:把「生命任务」从产出/身份剥出来,剩下的是「做个人、保持爱/受苦/怜悯/记忆」。当你的核心身份被砍掉(转行、被裁、项目死掉),剩下的「血肉」决定你能不能重新写——这是陀思妥耶夫斯基一百年后给 Frankl 的先声。For programmers today: strip 'life's task' of productivity and identity, and what remains is 'be a human being; keep loving, suffering, pitying, remembering.' When your core identity is cut off (a layoff, a pivot, a dead project), the 'flesh and blood' that's left determines whether you can start writing again — Dostoyevsky as a century-before-Frankl precursor.
工具角Tools Corner
- OnKey:先唱一遍,它就把歌学会了——本地训练的唱歌训练器OnKey: Sing a Song Once and It Learns the Melody — a Local Singing Trainer
- 点子:市面上唱歌软件都卖'预设曲目',OnKey 反过来——用你自己的音乐 App 播放,它听一遍就把旋律学进本地。The idea: singing apps all sell you preset songs; OnKey inverts it — play your own music app, and the app learns the melody locally after one listen.
- 做法:macOS 系统音频捕获 → 人声分离模型 → CREPE 追踪音高 → GAME 模型按音节切分成音符条,全程不上云(只向 Shazam/LRCLIB 要歌名和歌词元数据)。How: macOS system audio capture, a vocal-separation model, CREPE pitch tracking, and the GAME note model slicing into per-syllable note bars — all on-device (only Shazam/LRCLIB metadata leaves the Mac).
- 交互:歌结束时才学习;再放一遍,音符条向播放头滚动,你唱的音高画在条上,绿色=在调上,迟一点或低八度都不扣分。The interaction: it learns only when a song ends; on the next play the note bars scroll toward the playhead, your pitch draws over them, green when in tune; an octave down or a touch late is not penalized.
- 能带走什么:'学习在你机器上完成'作为隐私卖点,比任何隐私政策页面都管用。Takeaway: 'learning happens on your machine' as a privacy story is more convincing than any privacy-policy page.
- weave:按函数合并代码,而不是按行——给 AI 多智能体写的 git 合并驱动weave: Merge by Function, Not Line — an Entity-Level Git Merge Driver for Agent Teams
- 问题:git 按行合并。两个 agent 往同一个文件的不同函数里各加代码,行号重叠,git 报冲突——其实两个改动毫无关系。The problem: git merges by lines. Two agents add code to different functions of the same file; the line ranges overlap, git reports a conflict, even though the changes are unrelated.
- 关键想法:用 tree-sitter 把代码解析成实体(函数/类/键),做'实体级'三路合并——比的是两边在哪个实体上漂移了,而不是落在哪几行。The key idea: parse code into entities (functions, classes, keys) with tree-sitter and do an entity-level 3-way merge — comparing where each side drifted at the entity level, not which lines happened to collide.
- 结果:官方称冲突减少 ~95%(vs 行合并);剩下的真冲突会标 refused_by 说明为什么拒合,还带 MCP server 给 agent 框架用。The result: the project claims ~95% fewer conflicts versus line-based merging; real conflicts get a refused_by line explaining the refusal, plus an MCP server for agent frameworks.
- 能带走什么:'按结构而不是按行处理代码'是多 agent 协作的底层需求——这仓库把该需求做成了 git 合并驱动。Takeaway: 'structure rather than lines' is the foundational need of multi-agent collaboration — this repo turns that need into a git merge driver.
- Enron Brain:4.5 万封内部邮件,每个事实都引用出处The Enron Brain: 45k Internal Emails, Every Fact Citing Its Source Email
- 点子:拿 Enron 的 45,047 封邮件喂给 AI,让它写 214 页的公司/监管/银行实体页——没有一个人工编辑,每个事实都引用它来自哪封邮件。The idea: feed Enron's 45,047 emails to an AI and have it write 214 pages about the companies, regulators, and banks it dealt with — zero human editing, with every fact citing the email it came from.
- 关键设计:事实带'失效日期'——邮件显示某事不再为真时,页面那天自动过期;拖动时间滑块可以看到'那时我们知道什么'。The key design: facts carry expiry dates — when the mail shows a fact stopped being true, the page expires it on that date; a time slider shows 'what was known on this date.'
- 可信度:第二个 AI 做留出审计,抽查 49,401 个事实里 93% 被邮件完全支持,500 条核心抽查 0 条错。Trust: a held-out audit by a second AI found 93% of 49,401 sampled facts fully supported by their email, with 0 core errors in 500 samples.
- 能带走什么:'可过期知识'是 AI wiki 的稀缺设计——多数工具只会无限累积事实,不会撤回。Takeaway: 'knowledge that can expire' is the scarce design in AI wikis — most tools only accumulate facts, they never retract them.
- Swurf:把网页做成可滑的牌Swurf: The Real Web, As Swipeable Cards
- 点子:浏览器的交互是'一个页面一个标签页',Swurf 把网页变成可左右滑的卡片流,上下滚读当前那张。The idea: browsers treat a tab as one page; Swurf turns web pages into left/right-swipeable cards, scrolling within the card you're on.
- 关键设计:链接是可保存的'Swurf code'——把一段浏览历史(而不是单个 URL)分享给别人;还有'这不是本站'键让你能整站排除。The key design: links are savable 'Swurf codes' — you share a whole browsing session, not a single URL; an 'X out this site' key excludes entire domains.
- 能带走什么:把'浏览会话'当一等公民(可收藏、可分享)是 UI 里少见的好点子。Takeaway: treating a browsing session as a first-class, shareable artifact is an underrated UI move.