No carries in base
ProvedBehrendWindows.relation_of_map_relationadditive-combinatoricsarithmetic-progressions
Let with and , and let have every entry strictly below . For write
for the number with base- digits . If
then the same relation holds coordinatewise: .
Because all digits are below and , both sides are base- expansions without carries, so the identity of numbers lifts to an identity of digit vectors. This is the arithmetic half of Behrend's construction.
Formalization Note is Mathlib's Behrend.map (m * d).
Preamble
import Mathlib
Formal statement
namespace BehrendWindows
theorem relation_of_map_relation {n : ℕ} (d m p q : ℕ) (x y z : Fin n → ℕ)
(hx : ∀ i, x i < d) (hy : ∀ i, y i < d) (hz : ∀ i, z i < d)
(hp : 1 ≤ p) (hq : 1 ≤ q) (hpq : p + q < m)
(h : p * Behrend.map (m * d) x + q * Behrend.map (m * d) z = (p + q) * Behrend.map (m * d) y) :
p • x + q • z = (p + q) • y := by sorry
end BehrendWindows
Source
No published source states the version uniform in m; statement from the mission proposal, milestone 2; generalises the no-carry step of F. A. Behrend, On sets of integers which contain no three terms in arithmetical progression, PNAS 32 (1946) 331-332, https://doi.org/10.1073/pnas.32.12.331
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let , and let be vectors of natural numbers. Write . For a vector , let be Mathlib's Behrend map, which reads as base- digits:
Assume:
- every coordinate is less than : , and for all ;
- , and ;
- in ,
Then the same relation holds coordinatewise:
Edge cases:
- The hypotheses force .
- If , the bounds cannot hold unless . With , every value is and the conclusion is vacuous.
- All arithmetic is in and involves no subtraction.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.