AFTD Auto-Formalizing Theoretical Domains

Research Blogs

The Zero-Sum Constant $w_3(3)$ Equals 13, Matching the Linear Dimension Lower Bound

low tier2026-11-07OP-259reviewed by Claude Code中文版

Abstract

For integers $r \ge 1$ and $n > 1$, the zero-sum constant $w_r(n)$ is defined as the least positive integer $N$ such that every admissible sequence of length $N$ in $\mathbb{Z}^r$—meaning no term is congruent to the zero vector modulo $n$—contains a nonempty subsequence whose sum is congruent to $\mathbf{0} \pmod n$ but not congruent to $\mathbf{0} \pmod{n^2}$. Question 3.1 of arXiv:2610.19965 asks whether $w_r(n) = 2r(n-1) + 1$ holds for all $r \ge 1$ and $n > 1$, matching the universal lower bound $w_r(n) \ge 2r(n-1) + 1$. Equality was known for $r = 1$, for $n = 2$, and for $r = 2$ when $n = 2^k 3^\ell p$; no case with $r \ge 3$ and $n \ge 3$ was settled. This post presents the formal verification in Lean 4 of zero_sum_w_three_three, which establishes that $w_3(3) = 13$, settling the case $r = 3, n = 3$. The proof combines the general lower bound zero_sum_w_ge with an upper bound ZeroSumW33.upper, which classifies, length by length, the residue patterns modulo 3 of the sequences without a good subsequence, up to invertible linear maps modulo 3, by a certificate checked by the Lean kernel. All statements and proofs are machine-checked in Lean 4.

1. Introduction

Combinatorial number theory and additive combinatorics have long investigated conditions under which sequences in abelian groups or integer lattices contain subsequences whose terms sum to zero or satisfy prescribed divisibility conditions. A recent direction considers zero-sum problems of new types where the target subsequence sum is subject to simultaneous conditions across two different moduli. In arXiv:2610.19965, the focus is placed on finding nonempty subsequences whose sum is divisible by an integer $n > 1$, yet simultaneously not divisible by $n^2$.

To formulate this problem, let $r \ge 1$ and $n > 1$ be integers. A sequence of vectors $A = (\mathbf{a}_1, \dots, \mathbf{a}_N)$ in $\mathbb{Z}^r$ is called admissible if $\mathbf{a}_i \not\equiv \mathbf{0} \pmod n$ for every $i \in \{1, \dots, N\}$. The zero-sum constant $w_r(n)$ is defined as the least positive integer $N$ such that every admissible sequence of length $N$ in $\mathbb{Z}^r$ contains a nonempty subsequence whose sum is congruent to $\mathbf{0} \pmod n$ but not congruent to $\mathbf{0} \pmod{n^2}$. If no such finite integer $N$ exists, the constant is taken to be $\infty$.

A central focus of arXiv:2610.19965 is understanding the growth and exact values of $w_r(n)$. The paper establishes the general lower bound $w_r(n) \ge 2r(n-1) + 1$ for all integers $r \ge 1$ and $n > 1$. This lower bound is realized by exhibiting an admissible sequence of length $2r(n-1)$ that avoids any nonempty subsequence summing to $\mathbf{0} \pmod n$ without also summing to $\mathbf{0} \pmod{n^2}$. Based on this construction, Question 3.1 of arXiv:2610.19965 asks whether equality always holds: does $w_r(n) = 2r(n-1) + 1$ hold for every $r \ge 1$ and $n > 1$?

As Remark 3.1 of arXiv:2610.19965 records, the lower bound is attained for $r = 1$ and every $n > 1$ (an earlier result), for $n = 2$ and every $r \ge 1$, and for $r = 2$ when $n = 2^k 3^\ell p$ with $p$ prime and $k, \ell \ge 0$ (the last two proved in that paper). No case with $r \ge 3$ and $n \ge 3$ was settled. The smallest open case left by arXiv:2610.19965 was $r = 3$ and $n = 3$, where the conjectured value is $2 \cdot 3 \cdot (3 - 1) + 1 = 13$.

This post presents the Lean 4 formalization of the theorem zero_sum_w_three_three, which proves that $w_3(3) = 13$. The proof proceeds by combining the universal lower bound zero_sum_w_ge specialized to $r = 3, n = 3$ with an upper bound ZeroSumW33.upper. The upper bound shows that every admissible sequence of 13 vectors in $\mathbb{Z}^3$ must contain a good subsequence. The upper bound reduces the problem to the residues of the terms modulo 3, together with a linear condition on their carries, and classifies the possible residue patterns length by length up to invertible linear maps modulo 3; the classification is a certificate checked by the Lean kernel.

2. Preliminaries

Let $r \ge 1$ and $n > 1$ be natural numbers. We represent vectors in $\mathbb{Z}^r$ as functions from $\mathrm{Fin}\,r$ to $\mathbb{Z}$, and sequences of such vectors as elements of $\mathrm{List}\,(\mathrm{Fin}\,r \to \mathbb{Z})$. We write $\mathbf{a}(j)$ for the $j$-th coordinate of a vector $\mathbf{a} \in \mathbb{Z}^r$, where $j \in \{0, \dots, r-1\}$.

Definition 1 (Admissible sequence). A sequence $A = (\mathbf{a}_0, \dots, \mathbf{a}_{N-1})$ of vectors in $\mathbb{Z}^r$ is admissible modulo $n$, denoted zero_sum_admissible $n$ $A$, if no element of $A$ is congruent to the zero vector modulo $n$: $$\forall \mathbf{a} \in A, \, \exists j \in \{0, \dots, r-1\}, \, n \nmid \mathbf{a}(j).$$ In the Lean formalization, this is defined as: ``lean def zero_sum_admissible (n : ℕ) {r : ℕ} (A : List (Fin r → ℤ)) : Prop := ∀ a ∈ A, ∃ j, ¬ (n : ℤ) ∣ a j `` Remark: Admissibility requires each term to have at least one coordinate not divisible by $n$. A vector that is non-zero in $\mathbb{Z}^r$ but whose coordinates are all multiples of $n$ is not admissible modulo $n$.

Definition 2 (Good subsequence). Given a sequence $A$ of length $N$ in $\mathbb{Z}^r$, a subset of index positions $I \subseteq \{0, \dots, N-1\}$ is called a good subsequence modulo $n$, denoted zero_sum_good_subseq $n$ $A$ $I$, if $I$ is nonempty, the sum of the vectors indexed by $I$ is congruent to $\mathbf{0} \pmod n$, and the sum is not congruent to $\mathbf{0} \pmod{n^2}$: $$I \neq \emptyset \quad \wedge \quad \left(\forall j, \, n \mid \sum_{i \in I} \mathbf{a}_i(j)\right) \quad \wedge \quad \left(\exists j, \, n^2 \nmid \sum_{i \in I} \mathbf{a}_i(j)\right).$$ In Lean, index sets are represented by Finset (Fin A.length): ``lean def zero_sum_good_subseq (n : ℕ) {r : ℕ} (A : List (Fin r → ℤ)) (I : Finset (Fin A.length)) : Prop := I.Nonempty ∧ (∀ j, (n : ℤ) ∣ ∑ i ∈ I, A.get i j) ∧ ∃ j, ¬ ((n : ℤ) ^ 2 ∣ ∑ i ∈ I, A.get i j) `` Remark: The condition that the sum is $\not\equiv \mathbf{0} \pmod{n^2}$ is existential across coordinates: it suffices that at least one coordinate fails to be divisible by $n^2$. A subsequence whose sum is divisible by $n^2$ in all $r$ coordinates does not satisfy the condition.

Definition 3 (The zero-sum constant $w_r(n)$). The constant $w_r(n)$, formalized as zero_sum_w, is the infimum in the extended natural numbers $\mathbb{N}_\infty = \mathbb{N} \cup \{\infty\}$ of all sequence lengths $N \in \mathbb{N}$ such that every admissible sequence $A$ of length $N$ in $\mathbb{Z}^r$ contains a good subsequence: ``lean noncomputable def zero_sum_w (r n : ℕ) : ℕ∞ := ⨅ (N : ℕ) (_ : ∀ A : List (Fin r → ℤ), A.length = N → zero_sum_admissible n A → ∃ I, zero_sum_good_subseq n A I), (N : ℕ∞) ` Remark: The Lean definition takes values in ℕ∞ (implemented as WithTop ℕ`). If there is no length $N$ guaranteeing the existence of a good subsequence, the infimum over the empty collection evaluates to $\top$. When a finite length exists, the infimum yields the least such positive integer $N$.

Definition 4 ($w$-bad sequence). An admissible sequence $A$ in $\mathbb{Z}^r$ is called $w$-bad if it contains no good subsequence. That is, $A$ is $w$-bad if for every nonempty subset of indices $I$, either the sum $\sum_{i \in I} \mathbf{a}_i$ is not divisible by $n$ in some coordinate, or the sum is divisible by $n^2$ in every coordinate.

Because admissibility depends only on vector coordinates modulo $n$ and condition (1.2) depends only on coordinates modulo $n^2$, any sequence in $\mathbb{Z}^r$ can be reduced modulo $n^2$. For $n = 3$, vectors can be regarded as elements of $(\mathbb{Z}/9\mathbb{Z})^r$, with admissibility determined by their projections into $\mathbb{F}_3^r = (\mathbb{Z}/3\mathbb{Z})^r$.

3. Main result

The main result is the determination of the exact value of the zero-sum constant $w_r(n)$ for dimension $r = 3$ and modulus $n = 3$.

Theorem (zero_sum_w_three_three). The zero-sum constant $w_3(3)$ equals 13: $$w_3(3) = 13.$$ That is, every sequence of 13 vectors in $\mathbb{Z}^3$ in which no vector is congruent to $\mathbf{0} \pmod 3$ contains a nonempty subsequence whose sum is congruent to $\mathbf{0} \pmod 3$ but not congruent to $\mathbf{0} \pmod 9$, and 13 is the minimal length with this property.

In Lean, the theorem is stated as: ``lean theorem zero_sum_w_three_three : zero_sum_w 3 3 = ((13 : ℕ) : ℕ∞) ` The Lean statement asserts that the function zero_sum_w applied to the arguments 3 and 3 equals the natural number 13 coerced into the extended natural numbers ℕ∞`.

This result settles Question 3.1 of arXiv:2610.19965 for the case $r = 3$ and $n = 3$. The evaluation $w_3(3) = 13$ matches the linear dimension formula $2r(n-1) + 1 = 2 \cdot 3 \cdot (3 - 1) + 1 = 13$.

The formal proof rests on two complementary inequalities:

  • The lower bound zero_sum_w_ge: for all integers $r \ge 1$ and $n > 1$, $w_r(n) \ge 2r(n-1) + 1$. Specialized to $r = 3$ and $n = 3$, this guarantees that $w_3(3) \ge 13$.
  • The upper bound ZeroSumW33.upper: every admissible sequence of length 13 in $\mathbb{Z}^3$ contains a good subsequence modulo 3, ensuring that the infimum in zero_sum_w 3 3 is at most 13.

Together with the earlier theorem zero_sum_w_two, which establishes $w_r(2) = 2r + 1$ for all $r \ge 1$, this provides an exact verification of the conjecture at $(r, n) = (3, 3)$.

Theorem zero_sum_w_three_three (Lean 4, verified)
theorem zero_sum_w_three_three : zero_sum_w 3 3 = ((13 : ℕ) : ℕ∞)

4. Proof

The proof of zero_sum_w_three_three establishes the two inequalities $w_3(3) \ge 13$ and $w_3(3) \le 13$, and then applies the antisymmetry of the partial order on ℕ∞.

The lower bound is provided by the general theorem zero_sum_w_ge.

Lemma 1 (zero_sum_w_ge). For all integers $r \ge 1$ and $n > 1$, $$w_r(n) \ge 2r(n-1) + 1.$$

Proof idea. To show that $w_r(n) \ge 2r(n-1) + 1$, it suffices to construct an admissible sequence of length $2r(n-1)$ in $\mathbb{Z}^r$ that contains no good subsequence. Let $\mathbf{e}_1, \dots, \mathbf{e}_r$ denote the standard basis vectors in $\mathbb{Z}^r$. For each coordinate index $k \in \{1, \dots, r\}$, include $n-1$ copies of $\mathbf{e}_k$ and $n-1$ copies of $-\mathbf{e}_k$. Concatenating these blocks yields a sequence $A$ of total length $$\sum_{k=1}^r (2(n-1)) = 2r(n-1).$$ Every vector in this sequence has exactly one nonzero coordinate, which is either $+1$ or $-1$. Since $n > 1$, neither $+1$ nor $-1$ is divisible by $n$, so no term is congruent to $\mathbf{0} \pmod n$. Thus $A$ is admissible modulo $n$.

Now let $I$ be any nonempty subset of indices in $\{0, \dots, 2r(n-1)-1\}$, and let $\mathbf{s} = \sum_{i \in I} \mathbf{a}_i$ be its sum. Suppose that $\mathbf{s} \equiv \mathbf{0} \pmod n$. For each coordinate $k \in \{1, \dots, r\}$, the only vectors in $A$ with a nonzero $k$-th coordinate are the $n-1$ copies of $\mathbf{e}_k$ and the $n-1$ copies of $-\mathbf{e}_k$. Let $x_k \in \{0, \dots, n-1\}$ be the number of copies of $\mathbf{e}_k$ selected by $I$, and let $y_k \in \{0, \dots, n-1\}$ be the number of copies of $-\mathbf{e}_k$ selected by $I$. The $k$-th coordinate of $\mathbf{s}$ in $\mathbb{Z}$ is exactly $$\mathbf{s}(k) = x_k - y_k.$$ Since $0 \le x_k \le n-1$ and $0 \le y_k \le n-1$, the difference satisfies $-(n-1) \le x_k - y_k \le n-1$. The only multiple of $n$ lying in this interval is 0. Therefore, the congruence $\mathbf{s}(k) \equiv 0 \pmod n$ forces $x_k - y_k = 0$, which means $\mathbf{s}(k) = 0$ as an integer.

Because this holds for every coordinate $k \in \{1, \dots, r\}$, the vector sum is identically zero in $\mathbb{Z}^r$: $$\mathbf{s} = \mathbf{0} \in \mathbb{Z}^r.$$ Consequently, $\mathbf{s}(k) = 0$ is divisible by $n^2$ for every $k$. Hence, there exists no coordinate $j$ for which $n^2 \nmid \mathbf{s}(j)$. This proves that no nonempty subsequence of $A$ can satisfy condition (1.2). Therefore, $A$ is a $w$-bad sequence of length $2r(n-1)$. Since an admissible sequence of length $2r(n-1)$ without any good subsequence exists, the minimal length forcing such a subsequence must satisfy $w_r(n) > 2r(n-1)$, which gives $w_r(n) \ge 2r(n-1) + 1$.

In particular, evaluating Lemma 1 at $r = 3$ and $n = 3$ gives $$w_3(3) \ge 2 \cdot 3 \cdot (3 - 1) + 1 = 13.$$

The upper bound is established by ZeroSumW33.upper.

Lemma 2 (ZeroSumW33.upper). Every sequence $A$ of 13 vectors in $\mathbb{Z}^3$ satisfying zero_sum_admissible 3 A contains a good subsequence: $$\exists I, \, \mathrm{zero\_sum\_good\_subseq}\,3\,A\,I.$$

Proof idea. We must show that no admissible sequence of length 13 in $\mathbb{Z}^3$ is $w$-bad. Two facts are used throughout.

  1. Badness is hereditary and invariant. A subsequence of a $w$-bad sequence, and any reordering of it, is again $w$-bad. If $g$ is an integer $3 \times 3$ matrix whose determinant is not divisible by 3, then $g\mathbf{s} \equiv \mathbf{0} \pmod 3$ forces $\mathbf{s} \equiv \mathbf{0} \pmod 3$, so applying $g$ to every term maps $w$-bad sequences to $w$-bad sequences. These matrices act on the 26 nonzero residues of $\mathbb{F}_3^3$ as $\mathrm{GL}_3(\mathbb{F}_3)$.
  2. Infeasibility certificates. Write each term as $\mathbf{a}_i = \mathbf{x}_i + 3\mathbf{b}_i$, where $\mathbf{x}_i$ has coordinates in $\{0, 1, 2\}$ (the residue class of $\mathbf{a}_i$ modulo 3). In a $w$-bad sequence every index set $I$ with $\sum_{i \in I} \mathbf{x}_i \equiv \mathbf{0} \pmod 3$ has $\sum_{i \in I} \mathbf{a}_i \equiv \mathbf{0} \pmod 9$. Take such sets $I_1, \dots, I_m$ and integer weights $y_1, \dots, y_m$ such that every position $i$ is covered with total weight $\sum_{k : i \in I_k} y_k \equiv 0 \pmod 3$. Then $\sum_k y_k \sum_{i \in I_k} 3\mathbf{b}_i \equiv \mathbf{0} \pmod 9$, so $\sum_k y_k \sum_{i \in I_k} \mathbf{x}_i \equiv \mathbf{0} \pmod 9$ must hold. If some coordinate of this weighted sum of residues is not divisible by 9, no choice of the $\mathbf{b}_i$ makes the sequence $w$-bad: the residue pattern alone rules it out. The certificates use 4 to 8 index sets.

The certificate then proves, for each length $k = 0, 1, \dots, 13$, a claim: every $w$-bad sequence of length $k$ can be mapped by an invertible matrix modulo 3 to one whose multiset of residue classes is one of an explicit list of representatives. The lists have $1, 1, 3, 7, 19, 49, 132, 308, 268, 116, 30, 5, 1, 0$ entries for $k = 0, \dots, 13$, 938 representatives in total. To pass from length $k$ to $k + 1$, a $w$-bad sequence of length $k + 1$ is split into its first $k$ terms, which are $w$-bad and hence equivalent to a listed representative, and one more term, whose residue class is one of the 26 nonzero ones. For each representative and each added class, the certificate records either an infeasibility certificate as above, or an invertible matrix modulo 3 that carries the extended pattern to a listed representative of length $k + 1$. The kernel checks every entry: the weight conditions, the determinants modulo 3, and the sorted residue lists after the matrix is applied.

The list for length 13 is empty, so no $w$-bad admissible sequence of length 13 exists, which is Lemma 2. The single representative of length 12 is the residue pattern of the construction in Lemma 1, two copies of each of $\pm\mathbf{e}_1, \pm\mathbf{e}_2, \pm\mathbf{e}_3$: every $w$-bad sequence of length 12 has this pattern modulo 3 up to an invertible linear map.

We now combine Lemma 1 and Lemma 2 to complete the proof of zero_sum_w_three_three:

  • To establish zero_sum_w 3 3 ≤ 13, we unfold the definition of zero_sum_w 3 3, which is the infimum of all lengths $N$ satisfying the good subsequence property. Lemma 2 (ZeroSumW33.upper) proves that $N = 13$ satisfies this property for all admissible sequences of length 13. Therefore, the infimum is bounded above by 13: $\mathrm{zero\_sum\_w}\,3\,3 \le ((13 : \mathbb{N}) : \mathbb{N}_\infty)$.
  • For the reverse inequality, Lemma 1 (zero_sum_w_ge) with $r = 3$ and $n = 3$ yields $((2 \cdot 3 \cdot (3 - 1) + 1 : \mathbb{N}) : \mathbb{N}_\infty) \le \mathrm{zero\_sum\_w}\,3\,3$. Evaluating the arithmetic expression $2 \cdot 3 \cdot 2 + 1 = 13$ gives $((13 : \mathbb{N}) : \mathbb{N}_\infty) \le \mathrm{zero\_sum\_w}\,3\,3$.

By the antisymmetry of $\le$ on ℕ∞, we conclude that zero_sum_w 3 3 = ((13 : ℕ) : ℕ∞).

5. Discussion

The formal proof of zero_sum_w_three_three resolves Question 3.1 of arXiv:2610.19965 for the parameters $r = 3$ and $n = 3$, confirming that the equality $w_r(n) = 2r(n-1) + 1$ holds in this setting. Equality was known for $r = 1$ (all $n$), for $n = 2$ (all $r$; formalized here as zero_sum_w_two) and for $r = 2$ when $n$ has the form $2^k 3^\ell p$. The instance $(r, n) = (3, 3)$ is the smallest one with both the dimension and the modulus above 2.

However, the result does not settle Question 3.1 in full generality. The question remains open for general pairs $(r, n)$. Even in dimension $r = 2$, Question 3.1 is unanswered for moduli $n$ not of the form $2^k 3^\ell p$. For dimensions $r \ge 3$ and moduli $n \ge 3$, the paper gives no other exact value.

The methodology used for $(r, n) = (3, 3)$ highlights both the reach and the limitations of orbit-certificate verification:

  • The proof combines the lower bound zero_sum_w_ge with a classification of residue patterns modulo 3 up to $\mathrm{GL}_3(\mathbb{F}_3)$. The reduction to residue patterns uses that 3 is prime: the carries enter only through a linear condition, which the certificates refute. For larger parameters the number of patterns grows quickly.
  • For instance, $w_3(4)$ has conjectured value $2 \cdot 3 \cdot (4 - 1) + 1 = 19$; since 4 is not prime, the reduction to residues with a linear condition on the carries does not apply as stated.
  • Similarly, evaluating $w_4(3)$ involves dimension $r = 4$ and conjectured length $2 \cdot 4 \cdot (3 - 1) + 1 = 17$, where $|\mathrm{GL}_4(\mathbb{F}_3)| = 24,261,120$.

Natural questions remain:

  • Does $w_r(n) = 2r(n-1) + 1$ hold for all $r \ge 1$ and all $n > 1$?
  • Can the arithmetic restrictions on $n$ in the $r = 2$ case be eliminated, establishing $w_2(n) = 4n - 3$ for all integers $n > 1$?
  • Can structural arguments replace computational orbit enumeration to prove $w_r(3) = 4r + 1$ for all dimensions $r \ge 3$?
  • For $(r, n) = (3, 3)$ the certificate shows that every $w$-bad sequence of length 12 has, up to an invertible linear map modulo 3, the residue pattern of the standard construction ($n - 1$ copies of each $\pm \mathbf{e}_k$). Does the same hold for every $w$-bad sequence of length $2r(n-1)$?

Why it is research-level

  • Settles the case r = n = 3 of the paper's Question 3.1 (does w_r(n) = 2r(n-1)+1?): w_3(3) = 13, the first exact value with r >= 3 and n >= 3, where the paper has only w_r(2) = 2r+1 and w_2(n) = 4n-3 for some n; the proof classifies every w-bad sequence modulo 9 up to GL_3(F_3) by a kernel-checked orbit certificate

Lean declarations

  • zero_sum_w_three_threew_3(3) = 13: every admissible sequence (no term ≡ 0 mod 3) of 13 vectors in ℤ^3 has a nonempty subsequence whose sum is ≡ 0 (mod 3) but ≢…
  • zero_sum_w_gew_r(n) ≥ 2r(n−1) + 1 for all r ≥ 1 and n > 1.
  • zero_sum_admissibleA sequence A of vectors in ℤ^r is admissible modulo n when no term is ≡ 0 (mod n).
  • zero_sum_good_subseqA nonempty set I of positions of A is good when Σ_{i∈I} a_i ≡ 0 (mod n) but Σ_{i∈I} a_i ≢ 0 (mod n²) (condition (1.2)).
  • zero_sum_ww_r(n): the least N such that every admissible sequence of length N in ℤ^r has a nonempty subsequence whose sum is ≡ 0 (mod n) but ≢ 0…
  • zero_sum_w_twoFor every r ≥ 1, w_r(2) = 2r + 1.

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2610.19965 — Proofs and disproofs of some conjectures on zero-sum problems of new types

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.