Sperner systems with restricted differences

Chi Hoi Yip; Zixiang Xu

arxiv: 2210.02409 · v3 · submitted 2022-10-05 · 🧮 math.CO · math.NT

Sperner systems with restricted differences

Zixiang Xu , Chi Hoi Yip This is my paper

Pith reviewed 2026-05-24 10:17 UTC · model grok-4.3

classification 🧮 math.CO math.NT

keywords Sperner systemsdifferencing familiesmodular constraintsp-adic analysispolynomial methodSnevily theoremintersecting systems

0 comments

The pith

New upper bounds are obtained for q-modular L-differencing Sperner systems that improve on Frankl's bound and include the first q-modular analogue of Snevily's theorem.

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

The authors study families of subsets of [n] where the difference in sizes of symmetric differences between distinct members lies in a set L modulo q, with q a prime power. They prove new upper bounds on the size of such L-differencing Sperner systems using elementary p-adic analysis and the polynomial method. These bounds extend and improve Frankl's earlier result for the p-modular case. The techniques also yield new results on hypercube subsets with restricted distances and on L-avoiding L-intersecting families in the q-modular setting.

Core claim

The paper claims that q-modular L-differencing Sperner systems have size at most a quantity smaller than the sum from i=0 to |L| of binom(n,i), and that there is an analogue of Snevily's theorem stating that in the q-modular case, L-avoiding L-intersecting systems satisfy certain intersection theorems leading to new bounds, improving previous work and partially resolving an open question.

What carries the argument

q-modular L-differencing Sperner system, which is a set family where |A minus B| belongs to L modulo q, with the argument carried by applying p-adic valuations to indicator polynomials of the family.

If this is right

The maximum size is strictly less than Frankl's bound in many cases.
New upper bounds hold for subsets of the hypercube with restricted Hamming distances.
q-modular L-avoiding L-intersecting systems have improved size limits.
Previous results by Felszeghy, Hegedüs, and Rónyai are improved.
A question of Babai, Frankl, Kutin, and Štefankovič receives a partial answer.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The polynomial method combined with p-adics might apply to similar problems in other combinatorial settings with modular constraints.
These bounds could inform the design of constant weight codes with modular distance restrictions.
If the method generalizes beyond prime powers, it would cover all moduli.

Load-bearing premise

The p-adic valuation and polynomial method can be applied directly to the characteristic functions of the set families without introducing hidden dependencies on the choice of L or the prime power q that would invalidate the claimed improvement over Frankl's bound.

What would settle it

Constructing or exhibiting a q-modular L-differencing Sperner system whose cardinality exceeds the new upper bound derived in the paper for specific values of n, q, and L.

read the original abstract

Let $\mathcal{F}$ be a family of subsets of $[n]$ and $L$ be a subset of $[n]$. We say $\mathcal{F}$ is an $L$-differencing Sperner system if $|A\setminus B|\in L$ for any distinct $A,B\in\mathcal{F}$. Let $p$ be a prime and $q$ be a power of $p$. Frankl first studied $p$-modular $L$-differencing Sperner systems and showed an upper bound of the form $\sum_{i=0}^{|L|}\binom{n}{i}$. In this paper, we obtain new upper bounds on $q$-modular $L$-differencing Sperner systems using elementary $p$-adic analysis and polynomial method, extending and improving existing results substantially. Moreover, our techniques can be used to derive new upper bounds on subsets of the hypercube with restricted Hamming distances. One highlight of the paper is the first analogue of the celebrated Snevily's theorem in the $q$-modular setting, which results in several new upper bounds on $q$-modular $L$-avoiding $L$-intersecting systems. In particular, we improve a result of Felszeghy, Heged\H{u}s, and R\'{o}nyai, and give a partial answer to a question posed by Babai, Frankl, Kutin, and \v{S}tefankovi\v{c}.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first q-modular Snevily analogue and improves Frankl's bound on L-differencing Sperner systems with p-adic and polynomial methods.

read the letter

The main point is that this work extends Frankl's p-modular results to prime-power moduli q and supplies the first modular version of Snevily's theorem for L-avoiding L-intersecting families. It also derives new bounds on hypercube subsets with restricted Hamming distances and partially answers a question from Babai, Frankl, Kutin, and Stefankovic while improving on Felszeghy-Hegedüs-Rónyai. The techniques are described as elementary p-adic analysis plus the polynomial method, which is a reasonable way to handle the modular condition on differences. If the proofs are complete and the constants work out, this is a clean incremental advance inside extremal set theory. The paper does well by keeping the methods parameter-free and by stating explicit new upper bounds rather than just existence claims. The citation pattern looks standard and the claims do not appear to rest on fitted parameters or circular reductions. A soft spot is that the abstract gives no explicit constants, error terms, or sample calculations, so the actual size of the improvement over the sum of binomials bound is not visible without the full derivations. The assumption that the valuation applies directly to the characteristic functions without hidden L- or q-dependent issues also needs the details to confirm it holds. This is specialized work for people already reading papers on modular Sperner problems or coding-theory intersections. A reader who cares about q-modular extensions would get concrete new bounds and a new theorem to cite. It deserves peer review because the claims are specific, build on named prior results, and use standard tools in a new setting.

Referee Report

2 major / 0 minor

Summary. The paper defines q-modular L-differencing Sperner systems on the power set of [n] (q a prime power) and claims new upper bounds obtained via elementary p-adic analysis and the polynomial method. These bounds are asserted to improve substantially on Frankl's bound of sum_{i=0 to |L|} binom(n,i). The manuscript also derives a q-modular analogue of Snevily's theorem and applies it to obtain new bounds on q-modular L-avoiding L-intersecting families, improving a result of Felszeghy-Hegedüs-Rónyai and partially answering a question of Babai-Frankl-Kutin-Štefankovič. The techniques are further claimed to yield bounds on subsets of the hypercube with restricted Hamming distances.

Significance. If the stated bounds hold with explicit constants and the p-adic/polynomial methods apply directly to the characteristic functions without introducing L- or q-dependent artifacts that cancel the improvement, the work would constitute a notable advance in modular extremal set theory. The claimed first q-modular Snevily analogue is a highlight; the elementary and parameter-free character of the methods (as described) would be a further strength if the derivations are supplied.

major comments (2)

[Abstract] Abstract: the central claim of 'new upper bounds' and 'substantially improving' Frankl's result supplies neither the explicit form of the new bounds, nor error terms, nor a direct comparison constant, so the asserted improvement cannot be verified from the given text.
[Abstract] Abstract: the q-modular Snevily analogue is presented as a highlight, yet no statement of the precise theorem (including the modular condition on the intersection sizes) is supplied, which is load-bearing for assessing whether it genuinely extends the classical result.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful review and for highlighting the need for greater explicitness in the abstract. We agree that the abstract can be strengthened to make the main results more immediately verifiable and will revise it accordingly. Our point-by-point responses follow.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim of 'new upper bounds' and 'substantially improving' Frankl's result supplies neither the explicit form of the new bounds, nor error terms, nor a direct comparison constant, so the asserted improvement cannot be verified from the given text.

Authors: The explicit statements of the new upper bounds, including their dependence on q and L together with the direct comparison to Frankl's bound, appear in Theorems 3.1, 3.4 and 4.1 of the manuscript. We acknowledge that the abstract is too terse on this point and will revise it to include the leading term of the new bound and a brief indication of the improvement factor. revision: yes
Referee: [Abstract] Abstract: the q-modular Snevily analogue is presented as a highlight, yet no statement of the precise theorem (including the modular condition on the intersection sizes) is supplied, which is load-bearing for assessing whether it genuinely extends the classical result.

Authors: The precise statement of the q-modular Snevily analogue, including the required congruence condition on the intersection sizes modulo q, is given as Theorem 5.1. We will add a one-sentence formulation of this theorem to the abstract so that the modular extension is visible at a glance. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent analytic tools

full rationale

The paper derives new upper bounds for q-modular L-differencing Sperner systems via elementary p-adic analysis and the polynomial method, extending Frankl's combinatorial bound and yielding a q-modular analogue of Snevily's theorem. These steps invoke standard external techniques (p-adic valuations, polynomial interpolation) applied to characteristic functions without any reduction of the target bound to a fitted parameter, self-defined quantity, or load-bearing self-citation. The cited prior results (Frankl, Felszeghy et al., Babai et al.) are from distinct authors and serve only as baselines being improved upon. No equation or claim reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the p-adic and polynomial techniques are treated as standard tools imported from prior literature.

pith-pipeline@v0.9.0 · 5792 in / 1117 out tokens · 17938 ms · 2026-05-24T10:17:31.255248+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.4 ... If F ⊆ 2[n] is q-modular L-differencing Sperner, then |F| ≤ ∑_{i=0}^s binom(n-1,i) ... using elementary p-adic analysis and polynomial method
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Proposition 2.5 ... degree-d univariate polynomial g separating 0 from L + qZ ... |F| ≤ ∑_{i=0}^d binom(n-1,i)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

N. Alon. Perturbed identity matrices have high rank: pro of and applications. Combin. Probab. Comput. , 18(1- 2):3–15, 2009

work page 2009
[2]

N. Alon, L. Babai, and H. Suzuki. Multilinear polynomial s and Frankl–Ray-Chaudhuri–Wilson type intersection theorems. J. Combin. Theory Ser . A, 58(2):165–180, 1991

work page 1991
[3]

Babai, P

L. Babai, P . Frankl, S. Kutin, and D. ˇStefankoviˇ c. Set systems with restricted intersections modulo prime powers. J. Combin. Theory Ser . A, 95(1):39–73, 2001

work page 2001
[4]

Boros, V

E. Boros, V . Gurvich, and M. Milaniˇ c. Decomposing 1-Sperner hypergraphs. Electron. J. Combin., 26(3):Paper No. 3.18, 28, 2019

work page 2019
[5]

Boros, V

E. Boros, V . Gurvich, and M. Milaniˇ c. Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs. J. Graph Theory, 94(3):364–397, 2020

work page 2020
[6]

Cao, K.-W

W . Cao, K.-W . Hwang, and D. B. West. Improved bounds on fam ilies under k-wise set-intersection constraints. Graphs Combin., 23(4):381–386, 2007

work page 2007
[7]

Delsarte

P . Delsarte. Four fundamental parameters of a code and th eir combinatorial signiﬁcance. Information and Con- trol, 23:407–438, 1973

work page 1973
[8]

Erd˝ os, C

P . Erd˝ os, C. Ko, and R. Rado. Intersection theorems for s ystems of ﬁnite sets. Quart. J. Math. Oxford Ser . (2) , 12:313–320, 1961

work page 1961
[9]

Felszeghy, G

B. Felszeghy, G. Heged˝ us, and L. R´ onyai. Algebraic properties of modulo q complete l-wide families. Combin. Probab. Comput., 18(3):309–333, 2009

work page 2009
[10]

P . Frankl. Bounding the size of a family knowing the card inality of differences. Studia Sci. Math. Hungar ., 20(1- 4):33–36, 1985

work page 1985
[11]

P . Frankl. Antichains of ﬁxed diameter. Mosc. J. Comb. Number Theory , 7(3):3–33, 2017. 21

work page 2017
[12]

Frankl and N

P . Frankl and N. Tokushige. Extremal problems for ﬁnite sets , volume 86 of Student Mathematical Library . American Mathematical Society, Providence, RI, 2018

work page 2018
[13]

Frankl and R

P . Frankl and R. M. Wilson. Intersection theorems with g eometric consequences. Combinatorica, 1(4):357–368, 1981

work page 1981
[14]

Grolmusz

V . Grolmusz. Superpolynomial size set-systems with re stricted intersections mod 6 and explicit Ramsey graphs. Combinatorica, 20(1):71–85, 2000

work page 2000
[15]

Heged˝ us and L

G. Heged˝ us and L. R´ onyai. Standard monomials for q-uniform families and a conjecture of Babai and Frankl. Cent. Eur . J. Math., 1(2):198–207, 2003

work page 2003
[16]

Huang, O

H. Huang, O. Klurman, and C. Pohoata. On subsets of the hy percube with prescribed Hamming distances. J. Combin. Theory Ser . A, 171:105156, 21, 2020

work page 2020
[17]

D. J. Katz and J. Zahl. Bounds on degrees of p-adic separating polynomials. J. Combin. Theory Ser . A , 115(7):1310–1319, 2008

work page 2008
[18]

D. J. Kleitman. On a combinatorial conjecture of Erd˝ os . J. Combinatorial Theory, 1:209–214, 1966

work page 1966
[19]

S. Kutin. Constructing large set systems with given int ersection sizes modulo composite numbers. Combin. Probab. Comput., 11(5):475–486, 2002

work page 2002
[20]

Li and H

S. Li and H. Zhang. Set systems with L-intersections and k-wise L-intersecting families. J. Combin. Des. , 24(11):514–529, 2016

work page 2016
[21]

Liu and J

J. Liu and J. Liu. Set systems with cross L -intersection and k-wise L -intersecting families. Discrete Math. , 309(20):5920–5925, 2009

work page 2009
[22]

Liu and W

J. Liu and W . Y ang. Set systems with restricted k-wise L-intersections modulo a prime number. European J. Combin., 36:707–719, 2014

work page 2014
[23]

D. T. Nagy and B. Patk´ os. On L-close Sperner systems. Graphs Combin., 37(3):789–796, 2021

work page 2021
[24]

D. K. Ray-Chaudhuri and R. M. Wilson. On t-designs. Osaka Math. J., 12(3):737–744, 1975

work page 1975
[25]

H. S. Snevily. A sharp bound for the number of sets that pa irwise intersect at k positive values. Combinatorica, 23(3):527–533, 2003

work page 2003
[26]

E. Sperner. Ein Satz ¨ uber Untermengen einer endlichen Menge. Math. Z., 27(1):544–548, 1928

work page 1928
[27]

J. Xiao, J. Liu, and S. Zhang. Families of vector spaces w ith r-wise L-intersections. Discrete Math., 341(4):1041– 1054, 2018

work page 2018
[28]

Xu and J

J. Xu and J. Liu. A note on set families and codes. Ars Combin., 105:293–298, 2012. EXTREMAL COMBINATORICS AND PROBABILITY GROUP, I NSTITUTE FOR BASIC SCIENCE , D AEJEON , S OUTH KOREA Email address: zixiangxu@ibs.re.kr, or zxxu8023@qq.com DEPARTMENT OF MATHEMATICS , U NIVERSITY OF BRITISH COLUMBIA , 1984 M ATHEMATICS ROAD , V AN- COUVER V6T 1Z2, C ANADA ...

work page 2012

[1] [1]

N. Alon. Perturbed identity matrices have high rank: pro of and applications. Combin. Probab. Comput. , 18(1- 2):3–15, 2009

work page 2009

[2] [2]

N. Alon, L. Babai, and H. Suzuki. Multilinear polynomial s and Frankl–Ray-Chaudhuri–Wilson type intersection theorems. J. Combin. Theory Ser . A, 58(2):165–180, 1991

work page 1991

[3] [3]

Babai, P

L. Babai, P . Frankl, S. Kutin, and D. ˇStefankoviˇ c. Set systems with restricted intersections modulo prime powers. J. Combin. Theory Ser . A, 95(1):39–73, 2001

work page 2001

[4] [4]

Boros, V

E. Boros, V . Gurvich, and M. Milaniˇ c. Decomposing 1-Sperner hypergraphs. Electron. J. Combin., 26(3):Paper No. 3.18, 28, 2019

work page 2019

[5] [5]

Boros, V

E. Boros, V . Gurvich, and M. Milaniˇ c. Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs. J. Graph Theory, 94(3):364–397, 2020

work page 2020

[6] [6]

Cao, K.-W

W . Cao, K.-W . Hwang, and D. B. West. Improved bounds on fam ilies under k-wise set-intersection constraints. Graphs Combin., 23(4):381–386, 2007

work page 2007

[7] [7]

Delsarte

P . Delsarte. Four fundamental parameters of a code and th eir combinatorial signiﬁcance. Information and Con- trol, 23:407–438, 1973

work page 1973

[8] [8]

Erd˝ os, C

P . Erd˝ os, C. Ko, and R. Rado. Intersection theorems for s ystems of ﬁnite sets. Quart. J. Math. Oxford Ser . (2) , 12:313–320, 1961

work page 1961

[9] [9]

Felszeghy, G

B. Felszeghy, G. Heged˝ us, and L. R´ onyai. Algebraic properties of modulo q complete l-wide families. Combin. Probab. Comput., 18(3):309–333, 2009

work page 2009

[10] [10]

P . Frankl. Bounding the size of a family knowing the card inality of differences. Studia Sci. Math. Hungar ., 20(1- 4):33–36, 1985

work page 1985

[11] [11]

P . Frankl. Antichains of ﬁxed diameter. Mosc. J. Comb. Number Theory , 7(3):3–33, 2017. 21

work page 2017

[12] [12]

Frankl and N

P . Frankl and N. Tokushige. Extremal problems for ﬁnite sets , volume 86 of Student Mathematical Library . American Mathematical Society, Providence, RI, 2018

work page 2018

[13] [13]

Frankl and R

P . Frankl and R. M. Wilson. Intersection theorems with g eometric consequences. Combinatorica, 1(4):357–368, 1981

work page 1981

[14] [14]

Grolmusz

V . Grolmusz. Superpolynomial size set-systems with re stricted intersections mod 6 and explicit Ramsey graphs. Combinatorica, 20(1):71–85, 2000

work page 2000

[15] [15]

Heged˝ us and L

G. Heged˝ us and L. R´ onyai. Standard monomials for q-uniform families and a conjecture of Babai and Frankl. Cent. Eur . J. Math., 1(2):198–207, 2003

work page 2003

[16] [16]

Huang, O

H. Huang, O. Klurman, and C. Pohoata. On subsets of the hy percube with prescribed Hamming distances. J. Combin. Theory Ser . A, 171:105156, 21, 2020

work page 2020

[17] [17]

D. J. Katz and J. Zahl. Bounds on degrees of p-adic separating polynomials. J. Combin. Theory Ser . A , 115(7):1310–1319, 2008

work page 2008

[18] [18]

D. J. Kleitman. On a combinatorial conjecture of Erd˝ os . J. Combinatorial Theory, 1:209–214, 1966

work page 1966

[19] [19]

S. Kutin. Constructing large set systems with given int ersection sizes modulo composite numbers. Combin. Probab. Comput., 11(5):475–486, 2002

work page 2002

[20] [20]

Li and H

S. Li and H. Zhang. Set systems with L-intersections and k-wise L-intersecting families. J. Combin. Des. , 24(11):514–529, 2016

work page 2016

[21] [21]

Liu and J

J. Liu and J. Liu. Set systems with cross L -intersection and k-wise L -intersecting families. Discrete Math. , 309(20):5920–5925, 2009

work page 2009

[22] [22]

Liu and W

J. Liu and W . Y ang. Set systems with restricted k-wise L-intersections modulo a prime number. European J. Combin., 36:707–719, 2014

work page 2014

[23] [23]

D. T. Nagy and B. Patk´ os. On L-close Sperner systems. Graphs Combin., 37(3):789–796, 2021

work page 2021

[24] [24]

D. K. Ray-Chaudhuri and R. M. Wilson. On t-designs. Osaka Math. J., 12(3):737–744, 1975

work page 1975

[25] [25]

H. S. Snevily. A sharp bound for the number of sets that pa irwise intersect at k positive values. Combinatorica, 23(3):527–533, 2003

work page 2003

[26] [26]

E. Sperner. Ein Satz ¨ uber Untermengen einer endlichen Menge. Math. Z., 27(1):544–548, 1928

work page 1928

[27] [27]

J. Xiao, J. Liu, and S. Zhang. Families of vector spaces w ith r-wise L-intersections. Discrete Math., 341(4):1041– 1054, 2018

work page 2018

[28] [28]

Xu and J

J. Xu and J. Liu. A note on set families and codes. Ars Combin., 105:293–298, 2012. EXTREMAL COMBINATORICS AND PROBABILITY GROUP, I NSTITUTE FOR BASIC SCIENCE , D AEJEON , S OUTH KOREA Email address: zixiangxu@ibs.re.kr, or zxxu8023@qq.com DEPARTMENT OF MATHEMATICS , U NIVERSITY OF BRITISH COLUMBIA , 1984 M ATHEMATICS ROAD , V AN- COUVER V6T 1Z2, C ANADA ...

work page 2012