Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

No carries in base mdmdmd

Proved
BehrendWindows.relation_of_map_relation

by pitimespi · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

additive-combinatoricsarithmetic-progressions

Let n,d,m,p,q∈Nn,d,m,p,q\in\mathbb{N}n,d,m,p,q∈N with p,q≥1p,q\ge 1p,q≥1 and p+q<mp+q<mp+q<m, and let x,y,z∈Nnx,y,z\in\mathbb{N}^nx,y,z∈Nn have every entry strictly below ddd. For w∈Nnw\in\mathbb{N}^nw∈Nn write

ϕ(w)=∑i<nwi (md)i\phi(w)=\sum_{i<n} w_i\,(md)^iϕ(w)=i<n∑​wi​(md)i

for the number with base-(md)(md)(md) digits w0,…,wn−1w_0,\dots,w_{n-1}w0​,…,wn−1​. If

p ϕ(x)+q ϕ(z)=(p+q) ϕ(y),p\,\phi(x)+q\,\phi(z)=(p+q)\,\phi(y),pϕ(x)+qϕ(z)=(p+q)ϕ(y),

then the same relation holds coordinatewise: p x+q z=(p+q) yp\,x+q\,z=(p+q)\,ypx+qz=(p+q)y.

Because all digits are below ddd and p+q<mp+q<mp+q<m, both sides are base-(md)(md)(md) 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 ϕ\phiϕ 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 n,d,m,p,q∈Nn, d, m, p, q \in \mathbb{N}n,d,m,p,q∈N, and let x,y,z∈Nnx, y, z \in \mathbb{N}^nx,y,z∈Nn be vectors of natural numbers. Write B=mdB = m dB=md. For a vector w∈Nnw \in \mathbb{N}^nw∈Nn, let φB\varphi_BφB​ be Mathlib's Behrend map, which reads www as base-BBB digits:

φB(w)=∑i=0n−1wi Bi∈N.\varphi_B(w) = \sum_{i=0}^{n-1} w_i\, B^{i} \in \mathbb{N}.φB​(w)=i=0∑n−1​wi​Bi∈N.

Assume:

  • every coordinate is less than ddd: xi<dx_i < dxi​<d, yi<dy_i < dyi​<d and zi<dz_i < dzi​<d for all iii;
  • p≥1p \ge 1p≥1, q≥1q \ge 1q≥1 and p+q<mp + q < mp+q<m;
  • in N\mathbb{N}N,
p φmd(x)+q φmd(z)=(p+q) φmd(y).p\,\varphi_{md}(x) + q\,\varphi_{md}(z) = (p+q)\,\varphi_{md}(y).pφmd​(x)+qφmd​(z)=(p+q)φmd​(y).

Then the same relation holds coordinatewise:

p xi+q zi=(p+q) yifor every i∈{0,…,n−1}.p\,x_i + q\,z_i = (p+q)\,y_i \qquad \text{for every } i \in \{0,\dots,n-1\}.pxi​+qzi​=(p+q)yi​for every i∈{0,…,n−1}.

Edge cases:

  • The hypotheses force m≥3m \ge 3m≥3.
  • If d=0d = 0d=0, the bounds xi<0x_i < 0xi​<0 cannot hold unless n=0n = 0n=0. With n=0n = 0n=0, every φ\varphiφ value is 000 and the conclusion is vacuous.
  • All arithmetic is in N\mathbb{N}N and involves no subtraction.
Human review
  • Endorsed by Shuze Chen · Nov 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Nov 21, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me