Pith. sign in

REVIEW 4 minor 17 references

Code-based $[3,1]$-avoiders in finite affine spaces $\mathrm{AG}(n,2)$

T0 review · 0 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that every binary linear code builds an explicit set avoiding k-flats that meet it in one point, and that for k=3 these sets achieve exponentially many distinct sizes.

desk verdict A sound, incremental construction of [3,1]-avoiders with an exact size formula and an exponentially weak lower bound; the hard parts are correct. read the letter →

arxiv 2505.24072 v1 pith:MCXKUEO7 submitted 2025-05-29 math.CO

Benedek Kovács This is my paper
classification math.CO MSC 05B2594B05
keywords affinespacebinarylinearcodeweightenumeratorflatavoiderfreegroupping-ponglemmaspectrumdensityunavoidableintersections
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

For a set in the binary affine space $\mathbb{F}_2^n$, a $[3,1]$-flat is a 3-dimensional affine subspace meeting the set in exactly one point; the paper studies for which sizes $m$ every $m$-point set must force such a flat. It takes on the smallest open case of a conjecture that the density of such forced sizes tends to 1, and constructs explicit sets that avoid $[3,1]$-flats. The construction starts from any binary linear code $C$: for $n=\ell(k-1)$ it builds a $[k,1]$-avoider of size $2^n - W_C(1, 2^{k-1}-1)$, where $W_C$ is the weight enumerator of $C$. For even $n$, a family of codes built by two simple coordinate transformations yields at least about $2^{n/12}/\sqrt{n}$ distinct sizes of $[3,1]$-avoiders. These sizes are explicit witnesses against completeness of the spectrum, while a coding-theoretic upper bound shows the construction alone cannot refute the density conjecture.

What carries the argument

The load-bearing mechanism is the code-based construction: split coordinates into $\ell$ blocks of length $k-1$, map each affine point to its block-signature $s(x)\in\mathbb{F}_2^\ell$, and define $S_C=\{x: s(x)\notin C\}$. Counting points by signature gives $|S_C|=W_C(1,2^{k-1}-1)$, and the parity-check equations of $C$ rewrite $S_C$ as a union of symmetric differences of $(n-k+1)$-flats, exactly the sets that Observation 3.3 shows are $[k,1]$-avoiders. The diversity result runs on two length-increasing transformations $a$ and $b$; on the pair $(W_C(1,3), W_C(3,1))$ they act as the matrices $M_a=\mathrm{diag}(9,1)$ and $M_b=\begin{pmatrix}10&6\\6&10\end{pmatrix}$. The ping-pong lemma, applied to the cones $X_1=\{v: |y/x|<1/3 \text{ or } |y/x|>3\}$ and $X_2=\{v: 1/3<|y/x|<3\}$ in $\mathbb{Q}^2$, proves these matrices generate a free group, so distinct words give distinct matrices and hence many distinct first entries $\alpha_f+\beta_f$.

What would settle it

Compute, for all reduced words $w$ in the letters $a,b$ up to some length (say 12), the integer matrix product $M_w$, and look for a nontrivial $w$ with $M_w=I$; equivalently, test the ping-pong cone conditions of Proposition 5.6 by sampling vectors with $1/3<|y/x|<3$ and checking that $M_a^n v$ and $M_b^n v$ fall into the stated cones for all nonzero $n$. The first failure would dissolve the free-group claim and with it Theorem 1.6.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.5: fix $k\ge 3$ and $\ell\ge 1$; for any binary linear code $C\le \mathbb{F}_2^\ell$ and $n=\ell(k-1)$, there is a $[k,1]$-avoider $S_C$ in $\mathbb{F}_2^n$ with $|S_C|=2^n-W_C(1,2^{k-1}-1)$. The construction splits the coordinates into $\ell$ blocks of length $k-1$, sends each point to its block-signature in $\mathbb{F}_2^\ell$, and lets $S_C$ be the set of points whose signature is not a codeword of $C$; the parity-check equations express $S_C$ as a union of symmetric differences of $(n-k+1)$-flats, which Observation 3.3 classifies as $[k,1]$-avoiders. For $k=3$, the paper introduces two transformations that lengthen a code by two coordinates, tracks the pair $(W_C(1,3), W_C(3,1))$, and shows the transformations act as the matrices $M_a=\mathrm{diag}(9,1)$ and $M_b=\begin{pmatrix}10&6\\6&10\end{pmatrix}$. A ping-pong argument proves these matrices generate a free group of rank two, so the $2^r$ words of length $r$ give $2^r$ distinct matrices; a pigeonhole breakdown of the first entry of $M_f(1,1)^T$ then gives the lower bound of Theorem 1.6.

Load-bearing premise

The proof's lower bound rests on the assumption that the two numerical rules for updating a code's weight count are independent in the strong sense that no sequence of them cancels out; if two different sequences gave the same result, the exponential count of distinct sizes would collapse.

Editorial extensions

If this is right

  • Every binary linear code $C$ yields an explicit $[k,1]$-avoider whose size is the single evaluation $W_C(1,2^{k-1}-1)$, so new families of codes immediately produce new flat-avoiding sets.
  • For even $n$, the construction produces at least about $2^{n/12}/\sqrt{n}$ distinct sizes of $[3,1]$-avoiders, so the set of sizes that force a $[3,1]$-flat is missing at least exponentially many values, even though its density still tends to 1.
  • By Corollary 4.7, the code-based construction can produce at most $O(n c_k^n)$ distinct sizes for a constant $c_k<2$, so this method alone cannot refute Conjecture 1.1.
  • Since every $[3,1]$-avoider is also a $[k,1]$-avoider for $k\ge 4$ by partitioning flats, the same explicit sets work for higher-dimensional flats.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: If the author's Remark 5.7 is right, the first entries of $M_f(1,1)^T$ take nearly $2^r$ values, improving the lower bound to close to $2^{n/4}$ distinct sizes.
  • Editorial inference: The code-based trick is likely portable to other pairs $(k,t)$: any linear code family with many distinct weight-enumerator evaluations at the right inputs would give many avoider sizes, making Problems 4.3 and 4.4 the key quantity to study.
  • Editorial inference: A cheap numerical probe of the conjectured $(2-o(1))^r$ behavior is to sample random long words in $a,b$ and count distinct first entries; early saturation would indicate the free-group orbit separates values less strongly than hoped.
  • Editorial inference: Feeding known codes with structured weight enumerators into Theorem 1.5 could produce explicit, highly symmetric flat-avoiders of prescribed sizes, connecting the construction to classical code families.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies [k,1]-avoiders in binary affine spaces AG(n,2), i.e., subsets S such that no k-dimensional affine flat contains exactly one point of S. The main contribution is a code-based construction (Construction 4.1) that, given any binary linear code C of length ℓ and any fixed k ≥ 3, produces a [k,1]-avoider in F_2^{ℓ(k−1)} of size 2^n − W_C(1, 2^{k−1}−1), where W_C is the weight enumerator of C (Theorem 1.5). The paper then specializes to k=3 and, using two transformations a and b that increase code length by two, proves (Theorem 1.6) that for every even n ≥ 4 the construction yields at least binom(floor((n−4)/4), floor((n−4)/8))^{1/3} ≥ c·2^{n/12}/sqrt(n) distinct sizes of [3,1]-avoiders. The proof of the exponential lower bound uses the ping-pong lemma to show that the two matrices M_a=diag(9,1) and M_b=[[10,6],[6,10]] generate a free group of rank two, and then counts how many distinct first entries of M_f(1,1)^T arise as f ranges over words in {a,b}. The paper also gives an upper bound, via the MacWilliams identity, showing that the code-based construction cannot produce o(2^n) distinct sizes, so it does not contradict the authors' earlier density conjecture.

Significance. The result is a significant step on the smallest open case (k,t)=(3,1) of the Kovács–Nagy conjecture: it provides an explicit, deterministic family of [3,1]-avoiders with exponentially many different sizes, complementing earlier probabilistic evasive-set constructions. The code-based construction is elegant and reduces a geometric problem to weight-enumerator evaluations of binary linear codes, which is a new and potentially fruitful connection. The proof of Theorem 1.5 is self-contained and the size formula is exact; the free-group argument in Proposition 5.6 is correctly executed and constitutes the core of the exponential lower bound. The paper also correctly identifies a limitation of the method (Corollary 4.7), so the chief new result, Theorem 1.6, is appropriately placed as a lower bound rather than as a disproof of the conjecture.

minor comments (4)
  1. [Section 4, proof of Theorem 1.5] The displayed equation '|SC(k)| = sum_{c∈C} (2^{k−1}−1)^{ℓ−w(c)} = ... = W_C(1,2^{k−1}−1)' is not quite correct: SC(k) is defined as the set of x with s(x)∉C, so the sum gives the size of the complement {x : s(x)∈C}. The final equality |SC(k)| = 2^n − W_C(1,2^{k−1}−1) is correct, but the intermediate equation should be written as |{x : s(x)∈C}| = W_C(1,2^{k−1}−1).
  2. [Proposition 5.6, condition (2)] In the verification of the second ping-pong condition, for n≤−1 the ratio y′/x′ is stated to lie between −3 and −1/3, while X2 is defined using |y|/|x|. The claim is correct because |y′|/|x′| then lies in (1/3,3), but the wording should explicitly mention absolute values to match the definition of X2 and avoid confusion.
  3. [Proposition 4.5] In the ab<0 case, the expression for the upper bound is typeset as 2 \binom{|a|+|b|}{g}^ℓ + 1; it should read 2 · ((|a|+|b|)/g)^ℓ + 1. The surrounding text already explains the correct meaning, but the displayed formula as written is ambiguous.
  4. [Figure 1] The caption could be more precise by stating that the figure displays generator matrices for C, a(C), and b(C); currently it says 'generating matrices' without identifying the correspondence between the three matrices and the three codes.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the code-based construction and the free-group counting argument are self-contained; self-citations are contextual only.

full rationale

The paper's derivation chain is self-contained. Theorem 1.5 defines the avoider S_C(k) explicitly through a signature function, then computes its complement size directly as the weight-enumerator evaluation W_C(1, 2^{k-1}-1) and proves the [k,1]-avoiding property by expressing the complement as a union of symmetric differences of (n-k+1)-flats via the parity-check matrix. No fitted parameter is later renamed as a prediction, and no input is defined in terms of the target output. Theorem 1.6 tracks two weight-enumerator values under the transformations a and b through the matrices M_a = diag(9,1) and M_b = [[10,6],[6,10]], and the distinctness of the resulting sizes rests on the ping-pong lemma, an external standard result cited to de la Harpe, with explicit sets X1, X2 verifying the free-group claim in Proposition 5.6. The subsequent pigeonhole and determinant argument is independent of any fitted value. The self-citations to [10] and [11] concern the motivating conjecture and the independent-set counting problem, but are not load-bearing for the new construction or its counting proof. No circularity was found.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim relies only on standard coding theory and group theory results (MacWilliams identity, ping-pong lemma) and standard asymptotics. There are no hand-fitted constants, no free parameters, and no newly postulated entities. The only input is an arbitrary binary linear code C, which is a parameter of the construction, not a fitted quantity.

assumptions (4)
  • standard math MacWilliams identity relating weight enumerators of a code and its dual.
    Used in Proposition 4.6 to upper-bound the number of possible W_C(1,2^{k-1}-1) values, which limits the number of distinct avoider sizes from the code-based construction.
  • standard math Ping-pong lemma (free product criterion) of de la Harpe.
    Used in Proposition 5.6 to show M_a and M_b generate a free group of rank two, which is the key step for the exponential lower bound on distinct sizes.
  • standard math Stirling's asymptotic for binomial coefficients.
    Used at the end of Theorem 1.6 to convert the binomial lower bound into the exponential form c * 2^{n/12} / sqrt(n).
  • standard math Existence and basic properties of parity-check matrices for binary linear codes.
    Used in the proof of Theorem 1.5 to decompose the complement of S_C into a union of symmetric differences of flats.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Code-based $[3,1]$-avoiders in finite affine spaces $\mathrm{AG}(n,2)$." pith.science (2026). https://pith.science/paper/MCXKUEO7

@misc{pith2026250524072,
  author       = {Pith},
  title        = {Pith review of: Code-based $[3,1]$-avoiders in finite affine spaces $\mathrmAG(n,2)$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MCXKUEO7}},
  note         = {Machine review of arXiv:2505.24072}
}
abstract

The author, together with Nagy, studied the following problem on unavoidable intersections of given size in binary affine spaces. Given an $m$-element set $S\subseteq \mathbb{F}_2^n$, is there guaranteed to be a $[k,t]$-flat, that is, a $k$-dimensional affine subspace of $\mathbb{F}_2^n$ containing exactly $t$ points of $S$? Such problems can be viewed as generalizations of the cap set problem over the binary field. They conjectured that for every fixed pair $(k,t)$ with $k\ge 1$ and $0\le t\le 2^k$, the density of values $m\in \{0,...,2^n\}$ for which a $[k,t]$-flat is guaranteed tends to $1$. In this paper, motivated by the study of the smallest open case $(k,t)=(3,1)$, we present explicit constructions of sets in $\mathbb{F}_2^n$ avoiding $[k,1]$-flats for exponentially many sizes. These sets rely on carefully constructed binary linear codes, whose weight enumerators determine the size of the construction.

Figures

Figures reproduced from arXiv: 2505.24072 by the authors.

Figure 1
Figure 1. An example for the generating matrices of a code [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Blokhuis, A., Sziklai, P., & Sz˝ onyi, T. (2011). Blocking sets in projective spaces. Current research topics in Galois geometry, 61-84

    work page 2011

  2. [2]

    E., & Qin, H

    Bonin, J. E., & Qin, H. (2000). Size functions of subgeometry-closed classes of representable combinatorial geometries. Discrete Mathematics, 224(1-3), 37-60

    work page 2000

  3. [3]

    S., & Gijswijt, D

    Ellenberg, J. S., & Gijswijt, D. (2017). On large subsets of Fn q with no three-term arithmetic progression. Annals of Mathematics, 339-343

    work page 2017

  4. [4]

    L., & S´ os, V

    Erd˝ os, P., F¨ uredi, Z., Rothschild, B. L., & S´ os, V. T. (1999). Induced subgraphs of given sizes. Discrete Mathematics, 200(1-3), 61-77

    work page 1999

  5. [5]

    Guruswami, V. (2011). Linear-algebraic list decoding of folded Reed-Solomon codes, in Proceedings of the 26th IEEE Conference on Computational Complexity

    work page 2011

  6. [6]

    de la Harpe, P. (2000). Topics in geometric group theory. University of Chicago Press

    work page 2000

  7. [7]

    Hart, S. (1975). A note on the edges of the n-cube. Discrete Mathematics, Volume 14, Issue 2, 1976, 157-163

    work page 1975

  8. [8]

    Kasami, T., Tokura, N., & Azumi, S. (1976). On the weight enumeration of weights less than 2 .5d of Reed-Muller codes. Information and Control, 30(4), 380-395

    work page 1976

Show all 17 references
  1. [9]

    Kaufman, T., Lovett, S., & Porat, E. (2012). Weight distribution and list-decoding size of Reed-Muller codes. IEEE Transactions on Information Theory, 58(5), 2689-2696

    2012

  2. [10]

    Kov´ acs, B., & Nagy, Z. L. (2025). Avoiding intersections of given size in finite affine spaces AG( n, 2). Journal of Combinatorial Theory, Series A, 209, 105959

    2025

  3. [11]

    Kov´ acs, B., & Nagy, Z. L. (2025). Cardinalities of the total number of independent sets. Manuscript in preparation, submitted to arXiv on 30 May 2025

    2025

  4. [12]

    J., & Sloane, N

    MacWilliams, F. J., & Sloane, N. J. A. (1977). The theory of error-correcting codes (Vol. 16). Elsevier

    1977

  5. [13]

    McEliece, R. J. (1972). Weight congruences for p-ary cyclic codes. Discrete Mathematics, 3(1-3), 177-192

    1972

  6. [14]

    Prodinger, H., & Tichy, R. F. (1982). Fibonacci numbers of graphs. The Fibonacci Quarterly, 20(1), 16-21

    1982

  7. [15]

    Setyawan, Y. (1998). Combinatorial Number Theory: Results of Hilbert, Schur, Folkman, and Hindman. Simon Fraser University

    1998

  8. [16]

    Sloane, N., & Berlekamp, E. (1970). Weight enumerator for second-order Reed-Muller codes. IEEE Transactions on Information Theory, 16(6), 745-751

    1970

  9. [17]

    Tao, T., & Vu, V. H. (2006). Additive combinatorics (Vol. 105). Cambridge University Press. 11

    2006

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.