Pith. sign in

REVIEW 2 major objections 3 minor 31 references

Cardinalities of $g$-difference sets

T0 review · 2 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper proves the normalized minimal size of g-difference bases has a positive limit and that maximal g-difference sets have size √(gn).

desk verdict Theorem 1 is likely true but the proof has a real gap in Lemma 4 that the reader's take understates; the paper still deserves a referee. read the letter →

arxiv 2501.11736 v1 pith:T2QCBNOB submitted 2025-01-20 math.CO

Eric Schmutz , Michael Tait This is my paper · ORCID
classification math.CO MSC 11B1305B1011B3411N13
keywords g-differencebasesgeneralizedSidonsetsdifferencerepresentationfunctionsSingerBose-Chowlaadditivecombinatoricsfinitefieldsasymptoticextremalbounds
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

The paper studies two extremal quantities attached to a set $A$ of integers: the smallest size of $A$ such that every integer $1,\dots,n$ occurs at least $g$ times as a difference $a_1-a_2$, and the largest size of $A$ such that no nonzero integer occurs more than $g$ times as such a difference. It proves that the first quantity, divided by $\sqrt{n}$, converges to a positive finite constant, settling an open question from the literature and extending the known $g=1$ result. It proves that the second quantity is $(1+o_g(1))\sqrt{gn}$, giving the first-order size of generalized Sidon sets. For vector spaces over a fixed finite field it proves that the normalized minima have separate even-dimensional and odd-dimensional limits, and conjectures these limits differ. The upshot is that both the minimal and maximal problems follow the $\sqrt{n}$ scale, with the multiplicity $g$ entering the maximal problem exactly through a factor $\sqrt{g}$.

What carries the argument

The argument is carried by two classical constructions plus one weighting identity. For the minimal problem, a perfect difference set in the cyclic group of order $q^2+q+1$ is used to blow up any $g$-difference basis for $[v]$ into one for $[mv]$, while primes in short intervals let the blow-up be placed at the correct scale; iterating this forces $\liminf$ and $\limsup$ of $\eta_g(n)/\sqrt{n}$ together. For the upper bound on the maximal problem, the central identity is the weighted sum $\sigma_\ell = \sum_{t=1}^{\ell}\sum_{i=t+1}^{k}(a_i-a_{i-t})$ of consecutive differences, where cancellation gives an upper bound about $n\ell(\ell+1)/2$ and the at-most-$g$ representation condition gives a matching lower bound; choosing $\ell\approx\sqrt{k}$ yields $\alpha_g(n)\le(1+o(1))\sqrt{gn}$. For the lower bound, a Sidon set of size $q$ in $\mathbb{Z}/(q^2-1)\mathbb{Z}$ is quotiented by a subgroup of order $g$, producing a set whose nonzero differences each occur at most $g$ times in a cyclic group of size $N=(q^2-1)/g$, which is then embedded into $[n]$.

What would settle it

Compute, for fixed $g$ and increasingly large $n$, the actual primes $q\equiv1\pmod g$ in the interval $[\sqrt{(1-\varepsilon)gn}+1,\sqrt{gn}+1]$; if infinitely many of these intervals contain no prime with $(q^2-1)/g\le n$, then the embedding step in Proposition 2 fails and the lower-bound proof would need a different construction.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the normalized sequence $\eta_g(n)/\sqrt{n}$ has a positive finite limit for every fixed $g$, not merely bounded oscillation, and that the companion maximum $\alpha_g(n)$ satisfies $\alpha_g(n)=(1+o_g(1))\sqrt{gn}$. The first statement answers the existence question posed for generalized difference bases; the second pins down the constant for sets with at most $g$ representations of each nonzero difference. In vector spaces over a finite field, the paper proves that the corresponding even and odd subsequential limits exist and conjectures that they are unequal, signaling a parity effect in that setting.

Load-bearing premise

The lower-bound proof for $\alpha_g(n)$ assumes that for every large $n$ one can find a prime $q$ with $q\equiv1\pmod g$ and $q^2-1\le gn$, so that the cyclic construction of size $q$ actually sits inside $[n]$; the interval used in the proof only guarantees $q\le\sqrt{gn}+1$, which is not by itself enough.

Editorial extensions

If this is right

  • For every fixed $g$, the minimal $g$-difference basis problem has a true asymptotic scale: $\eta_g(n)=C_g\sqrt{n}(1+o(1))$ for some positive constant $C_g$, so comparisons between different $g$ reduce to comparing constants.
  • The maximal size of a subset of $[n]$ with no difference repeated more than $g$ times is $(1+o(1))\sqrt{gn}$, settling the first-order behaviour of generalized Sidon sets.
  • The lower-bound construction gives explicit sets of size $(1-o(1))\sqrt{gn}$ with the required representation bound, so the asymptotic is achieved rather than merely approached by counting.
  • In $\mathbb{F}_p^n$, $\eta_g$ has separate even and odd limits; if the conjecture is correct, the parity of the dimension is asymptotically visible in the minimal difference-basis size.
  • The upper-bound method yields a quantitative route: taking $\ell\approx\sqrt{k}$ in the weighted sum controls $\alpha_g(n)$ to within $o(\sqrt{gn})$, so the result is not just an order-of-magnitude statement.

Reading between the lines

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

  • The proof of Proposition 2 asserts that $q\le\sqrt{gn}+1$ implies $(q^2-1)/g\le n$; this implication is not valid in general (for example $g=2,n=3$ gives $q=3$ but $(q^2-1)/g=4>3$), so as written the lower bound relies on a prime selection slightly stronger than the one stated, likely fixable because the required interval still has length growing like $\sqrt{n}$.
  • The quotient-of-Sidon-set construction suggests a transfer principle: any group with a difference set of size about $\sqrt{N}$ should admit $g$-restricted difference sets of size about $\sqrt{gN}$, which would generalize Theorem 3 to other cyclic and abelian settings.
  • The even/odd split in $\mathbb{F}_p^n$ parallels known behaviour for sum-side quantities and hints that the asymptotic constant for vector spaces may depend on whether the dimension is even; testing the conjecture numerically for small $p$ and large $k$ would be a direct check.
  • A plausible strengthening of Theorem 1 would be an explicit value or bounds for the limiting constant $C_g$; the paper shows existence but leaves its numerical determination open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies two extremal functions for difference representations in [n]: η_g(n), the minimum size of a set A ⊂ Z with at least g representations of every x ∈ [n], and α_g(n), the maximum size of A ⊂ [n] with at most g representations of every nonzero x. The main results are Theorem 1, asserting that lim_{n→∞} η_g(n)/√n exists and is positive, answering a question of Kravitz, and Theorem 3, asserting that α_g(n) = (1 + o_g(1))√(gn). Theorem 2 gives analogous but parity-dependent limits for η_g(F_p^n)/√(p^n). The proofs use a Rédei–Rényi/Singer construction for the lower bound side of η_g, product and induction constructions for F_p^n, and a Bose–Chowla/Siegel–Walfisz construction for α_g. The paper also surveys sum analogues and applications to coding theory and cryptography.

Significance. If the main theorems hold, they resolve Kravitz's limit-existence question and determine the first-order asymptotic of generalized Sidon sets in [n], improving the Θ(√(gn)) bounds of Xu. The paper connects classical tools — Singer difference sets, Rédei–Rényi's argument, and Bose–Chowla sets — in a clean way, and the applications discussion is useful context. However, two load-bearing constructions contain gaps: Lemma 4 omits one Singer element, and Proposition 2's prime interval does not imply the required N ≤ n. Both gaps appear local and repairable, but the proofs as written do not establish the theorems.

major comments (2)
  1. [Section 2.3, Lemma 4 and Corollary 3] Lemma 4 is false as stated. Singer's Lemma 3 supplies q + 1 elements a_0, ..., a_q whose q^2 + q ordered differences exhaust the nonzero residues modulo m = q^2 + q + 1. The set F is defined with i = 1, ..., q only. The q(q − 1) ordered differences among these q elements cover at most q^2 − q nonzero residues, leaving 2q residues uncovered (namely the differences a_0 − a_i and a_i − a_0). Consequently, in Case 2 of the proof, the assertion that Singer's theorem gives r = a_h − a_ℓ or r − m = a_h − a_ℓ for some h, ℓ is false when the required difference involves the omitted index 0; the proof also silently omits the case r = 0. Since Corollary 3 and the Rédei–Rényi argument of Theorem 1 use exactly the bound |F| = q η_g(v), the proof of Theorem 1 is not valid as written. A repair using all q + 1 Singer elements would change Corollary 3 to η_g(n) ≤ (q_n + 1)η_g(v), and the constants in the proof of Theorem 1 would then need to be rechecked; this appears feasible, but it is not the proof in the manuscript.
  2. [Section 4.2, Proposition 2] The displayed prime interval √((1−ε)gn) + 1 ≤ q ≤ √(gn) + 1 does not imply (q^2 − 1)/g ≤ n. For q = √(gn) + 1 one has (q^2 − 1)/g = n + 2√(n/g), which can exceed n. Thus the constructed set of representatives need not lie in [n], and the claimed lower bound α_g(n) ≥ (1 − o(1))√(gn) rests on a stronger prime-selection statement that is not proved. This is also repairable: replacing the upper endpoint with √(gn + 1) gives N ≤ n, and existence of a prime q ≡ 1 (mod g) in the resulting interval follows from Siegel–Walfisz for the fixed modulus g, but the manuscript must state and justify this corrected condition.
minor comments (3)
  1. [Section 4.2, Lemma 8] Lemma 8 is not self-contained: its statement refers to 'The set A is defined below in the statement of Proposition 2.' It should be reformulated in terms of A_H or in terms of the quotient construction.
  2. [Section 4.1, Equation (10)] In the parenthetical expansion following Equation (10), there is an apparent typo: 'dg+' should read 'd_{2g}'.
  3. [Section 5.1] The definition of r_{A+A}(s) contains a spurious semicolon: 's = a + a; }' should be 's = a + a}'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central theorems are derived from external constructions and bounds, not from their own conclusions.

full rationale

The paper's main claims rest on independent mathematical inputs rather than on fitted or self-referential quantities. Theorem 1 is a liminf/limsup contradiction argument: it selects v with η_g(v)/√v near the liminf L and then uses Singer's difference sets and Baker–Harman–Pintz primes to show that all sufficiently large η_g(n)/√n are below L+(U−L)/3. No parameter is fitted to the target limit, and no prediction is defined in terms of the data it purportedly explains. Theorem 3's upper bound is a Lindström-style summation bound, and its lower bound is a construction from Bose–Chowla Sidon sets, a quotient by a subgroup H, and Siegel–Walfisz primes; neither direction uses the theorem's own conclusion as an input. The only self-citation of note is Lemma 8, cited to [19] (coauthored by Tait) and also to the independent paper [15]; it is a standard Sidon-set fact and does not carry the main asymptotic. There are genuine correctness gaps outside circularity: Lemma 4 uses only q of Singer's q+1 elements and therefore does not cover all residues as claimed, and Proposition 2's assertion that q²−1 ≤ gn follows from q ≤ √(gn)+1 is not justified; the displayed interval only gives q²−1 ≤ gn+2√(gn), not q²−1 ≤ gn. These are mathematical errors or missing justifications, not cases where a result is equivalent to its inputs by construction. The paper is therefore not circular in the sense this pass is asked to detect.

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

The proof relies on standard external number theory: Singer's difference sets, the Baker-Harman-Pintz prime gap theorem, the Siegel-Walfisz theorem, and Bose-Chowla Sidon sets. Lemma 8 is a known property of the Bose-Chowla set and is cited to an external source in addition to a paper coauthored by Tait. There are no fitted parameters; the constant 100 in Lemma 7 is an arbitrary proof convenience, not a parameter the final asymptotic depends on. No invented entities are introduced.

assumptions (5)
  • standard math Singer's theorem: for prime q and m = q^2+q+1, there are q+1 integers whose nonzero differences represent every residue 1,...,m-1 modulo m.
    Used in Lemma 4 to cover all slots s = km + r in the product construction.
  • standard math Baker-Harman-Pintz theorem: for all sufficiently large x there is a prime in [x - x^0.525, x].
    Used in Condition 2 of Theorem 1 to choose q_n between √(n/v) and (1 + δ/(10g))√(n/v).
  • standard math Siegel-Walfisz theorem: primes congruent to 1 mod g are asymptotically distributed as x/(φ(g) log x).
    Used in Proposition 2 to choose q ≡ 1 mod g near √(gn).
  • standard math Bose-Chowla theorem: B_q = {a : θ^a − θ ∈ F_q} is a Sidon set of size q in Z/(q^2−1)Z.
    Used in Proposition 2 to build the set AH.
  • standard math Lemma 8 from [15,19]: the Bose-Chowla set has no nonzero difference inside the subgroup H of order g.
    Load-bearing for the quotient construction; cited to an independent external source [15] as well as [19].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cardinalities of $g$-difference sets." pith.science (2026). https://pith.science/paper/T2QCBNOB

@misc{pith2026250111736,
  author       = {Pith},
  title        = {Pith review of: Cardinalities of $g$-difference sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T2QCBNOB}},
  note         = {Machine review of arXiv:2501.11736}
}
abstract

Let $\eta_{g}(n) $ be the smallest cardinality that $A\subseteq {\mathbb Z}$ can have if $A$ is a $g$-difference basis for $[n]$ (i.e, if, for each $x\in [n]$, there are {\em at least} $g$ solutions to $a_{1}-a_{2}=x$ ). We prove that the finite, non-zero limit $\lim\limits_{n\rightarrow \infty}\frac{\eta_{g}(n)}{\sqrt{n}}$ exists, answering a question of Kravitz. We also investigate a similar problem in the setting of a vector space over a finite field. Let $\alpha_g(n)$ be the largest cardinality that $A\subseteq [n]$ can have if, for all nonzero $x$, $a_{1}-a_{2}=x$ has {\em at most} $g$ solutions. We also prove that $\alpha_g(n)={\sqrt{gn}}(1+o_{g}(1))$ as $n\rightarrow\infty$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    R. C. Baker, G. Harman, and J. Pintz, The difference betwee n consecutive primes. II, Proc. Lond. Math. Soc. (3) 83 (3) (2001), 532–562

    work page 2001

  2. [2]

    Balogh, Z

    J. Balogh, Z. F¨ uredi, and S. Roy, An upper bound on the siz e of Sidon sets, Amer. Math. Monthly 130 (5) (2023), 437–445

    work page 2023

  3. [3]

    Bartoli, A

    D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini, an d F. Pambianco, New bounds for linear codes of covering radius 2, in Lecture Notes in Comput. Sci. , 10495 Springer, 2017, pp. 1–10

    work page 2017

  4. [4]

    Bartoli, A

    D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini, an d F. Pambianco, New bounds for linear codes of covering radii 2 and 3, Cryptogr. Commun. 11 (2019), 903–920. 17

    work page 2019

  5. [5]

    Bernshteyn and M

    A. Bernshteyn and M. Tait, Improved lower bound for differ ence bases, J. Number Theory 205 (2019), 50–58

    work page 2019

  6. [6]

    R. C. Bose and S. Chowla, Theorems in the additive theory o f numbers, Comment. Math. Helv. 37 (1962/63), 141–147

    work page 1962

  7. [7]

    Brauer, A problem of additive number theory and its app lication in electrical engineering, J

    A. Brauer, A problem of additive number theory and its app lication in electrical engineering, J. Elisha Mitchell Sci. Soc. 61 (1945), 55–66

    work page 1945

  8. [8]

    Carlet, On APN exponents, characterizations of differ entially uniform functions by the Walsh transform, and related cyclic-difference-set- like structures, Des

    C. Carlet, On APN exponents, characterizations of differ entially uniform functions by the Walsh transform, and related cyclic-difference-set- like structures, Des. Codes Cryptogr. 87 (2019), 203–224

    work page 2019

Show all 31 references
  1. [9]

    Carlet, Boolean functions for cryptography and coding theory, Cambridge University Press, New York, 2020

    C. Carlet, Boolean functions for cryptography and coding theory, Cambridge University Press, New York, 2020

    2020

  2. [10]

    Carter, Z

    D. Carter, Z. Hunter, and K. O’Bryant, On the diameter of finite Sidon sets, preprint, arXiv:2310.20032

    arXiv

  3. [11]

    Cilleruelo, I

    J. Cilleruelo, I. Ruzsa, and C. Vinuesa, Generalized Si don sets, Adv. Math. 225 (5) (2010), 2786–2807

    2010

  4. [12]

    Czerwinski and A

    I. Czerwinski and A. Pott, Sidon sets, sum-free sets and linear codes, Adv. Math.Commun. 18 (2) (2024), 549–566

    2024

  5. [13]

    A. A. Davydov, Constructions and families of nonbinary linear codes with covering radius 2, IEEE Trans. Inform. Theory 45 (5) (1999), 1679–1686

    1999

  6. [14]

    A. A. Davydov and P. Ostergard, Linear codes with coveri ng radius R = 2 ,3 and codimension tR, IEEE Trans. Inform. Theory 47 (1) (2001), 416–421

    2001

  7. [15]

    D. F. Daza, C. A. Trujillo, and F. A. Benavides, Sidon set s and C4-saturated graphs, preprint, arXiv:1810.05262

    arXiv

  8. [16]

    Graham and N

    R. Graham and N. Sloane, On the covering radius of codes, IEEE Trans. Inform. Theory 31 (3) (1985), 385–401

    1985

  9. [17]

    R. L. Graham and N. J. A. Sloane, On additive bases and har monious graphs, SIAM SIAM J. Algebraic Discrete Methods 1 (4) (1980), 382–404

    1980

  10. [18]

    Green, 100 open problems, manuscript, available on request to Professor Green (accessed November 2024) (2024)

    B. Green, 100 open problems, manuscript, available on request to Professor Green (accessed November 2024) (2024)

    2024

  11. [19]

    Johnston, M

    G. Johnston, M. Tait, and C. Timmons, Upper and lower bou nds on the size of Bk[g] sets, Australas. J. Combin. 83 (1) (2022), 129–140

    2022

  12. [20]

    Kravitz, Generalized difference sets and autocorrel ation integrals, (preprint, arXiv: 2004.06611 [math.co] ), Acta Arith

    N. Kravitz, Generalized difference sets and autocorrel ation integrals, (preprint, arXiv: 2004.06611 [math.co] ), Acta Arith. 199 (2) (2021), 199–219

    2021 arXiv

  13. [21]

    Lindstr¨ om, An inequality for B2-sequences, J

    B. Lindstr¨ om, An inequality for B2-sequences, J. Combin. Theory 6 (2) (1969), 211–212. 18

    1969

  14. [22]

    Mirsky, MathSciNet Review MR003055

    L. Mirsky, MathSciNet Review MR003055. Mirsky’s revie w outlines R´ edei and R´ enyi’s proof in English

  15. [23]

    G. P. Nagy, Thin Sidon sets and the nonlinearity of vecto rial boolean functions, preprint, arXiv:2212.05887

    arXiv

  16. [24]

    Nyberg, Perfect nonlinear S-boxes, in Lecture Notes in Comput

    K. Nyberg, Perfect nonlinear S-boxes, in Lecture Notes in Comput. Sci., 547 Springer, 1991, pp. 378–386

    1991

  17. [25]

    O’Bryant, A complete annotated bibliography of work related to Sidon sequences, preprint, arXiv: 0407117 [math]

    K. O’Bryant, A complete annotated bibliography of work related to Sidon sequences, preprint, arXiv: 0407117 [math]

  18. [26]

    Plagne, Recent progress on finite Bh[g] sets, Congr

    A. Plagne, Recent progress on finite Bh[g] sets, Congr. Numer. (2001), 49–64

    2001

  19. [27]

    R´ edei and A

    L. R´ edei and A. R´ enyi, On the representation of the num bers 1 ,2,· · ·, N by means of differences, Mat. Sbornik N.S. 24/66 (1949), 385–389

    1949

  20. [28]

    Sidon, Ein satz ¨ uber trigonometrische polynome und seine anwendung in der the- orie der Fourier-reihen, Math

    S. Sidon, Ein satz ¨ uber trigonometrische polynome und seine anwendung in der the- orie der Fourier-reihen, Math. Ann. 106 (1) (1932), 536–539

    1932

  21. [29]

    Singer, A theorem in finite projective geometry and so me applications to number theory, Trans

    J. Singer, A theorem in finite projective geometry and so me applications to number theory, Trans. Amer. Math. Soc. 43 (3) (1938), 377–385

    1938

  22. [30]

    Tait and R

    M. Tait and R. Won, Improved bounds on sizes of generaliz ed caps in AG(n, q), SIAM J. Discrete Math. 35 (1) (2021), 521–531

    2021

  23. [31]

    Xu, Popular differences and generalized Sidon sets, J

    W. Xu, Popular differences and generalized Sidon sets, J. Number Theory 186 (2018), 103–120. 19

    2018

Pith tools

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