Pith. sign in

REVIEW 5 minor 11 references

Solution to a conjecture of Alon, D\k{e}bski, Grytczuk and Przyby\l{}o on fixed-cardinality arithmetic progressions

T0 review · 0 major / 5 minor · reviewed 2026-07-08 · glm-5.2

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

Pith's one-line read Arithmetic progressions pack into near-optimal intervals

desk verdict Resolves the Alon–Dębski–Grytczuk–Przybyło conjecture with a clean, correct argument. Deserves a serious referee. read the letter →

arxiv 2607.06113 v1 pith:CXUXZXFB submitted 2026-07-07 math.CO

Yaping Mao , Zhao Wang , Meiqin Wei , Gang Yang This is my paper
classification math.CO MSC 05D1505C6511B25
keywords arithmeticprogressiontranslated-setpackingrainbowmatchingrandompartitionLYMinequalityhypergraphcombinatorial
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 resolves a conjecture by Alon, Dębski, Grytczuk, and Przybyło about how efficiently one can pack translated arithmetic progressions into a single interval. For each d from 1 to k, the set B_d = {d, 2d, ..., nd} is an n-term arithmetic progression with common difference d. The question is: what is the shortest interval [m] that can contain one disjoint translate of each B_1, ..., B_k? A trivial counting argument shows m must be at least nk, since there are k sets each of size n. The authors prove that for every fixed n and any epsilon > 0, once k is large enough, m is at most n times ceiling of (1+epsilon)k, which means the packing achieves the trivial lower bound asymptotically: M_k(n) = (1 + o(1))nk. The difficulty is that the progressions become longer and more rigid as d grows, so naive placement strategies leave too much wasted space. The proof combines a random partition of an integer interval whose expected part sizes follow a harmonic law (1/d), the LYM inequality to control how concentrated any single progression length can be at any point, and a rainbow matching theorem of Delcourt and Postle to convert a fractional packing into an integral one.

What carries the argument

Random harmonic partition (Lemma 2.2), LYM inequality for spread control (Lemma 2.4), Delcourt–Postle full rainbow matching theorem (Theorem 2.1)

What would settle it

If the Delcourt–Postle theorem (Theorem 2.1) fails for the parameter ranges used here, or if the union bound in Lemma 4.1 does not hold with positive probability for all four conditions simultaneously, the integral packing would not follow from the fractional one.

Watch

Extended reading notes

Core claim

The central mechanism is a three-stage pipeline from fractional to integral packing. First, a random partition of an interval of length L into parts of size at most k is constructed so that the expected number of parts of size d equals L/(kd), a harmonic identity that, after normalization, assigns total mass 1/d to intervals of length d. Second, ordering the parts randomly and applying the LYM inequality shows that no single progression length d contributes too much weight at any single point, yielding a fractional packing with uniform total load k/L at every point. Third, each interval of length d is replaced by d disjoint n-term arithmetic progressions of common difference d, and the Del-–

Load-bearing premise

The final step from a fractional packing to an actual disjoint placement relies on the Delcourt–Postle rainbow matching theorem being correct; without it, the construction produces only a weighted (fractional) packing, not a real one.

Editorial extensions

If this is right

  • For n=2, the result recovers the classical Skolem sequence theory: pairs with distances 1 through k can pack into an interval of length 2k or 2k+1 depending on k mod 4, which is exactly (1+o(1))2k.
  • For n≥3, the asymptotic result is established but exact tiling questions remain open — it is unknown for which pairs (n,k) an interval of length exactly nk can be perfectly partitioned into n-term arithmetic progressions with differences 1 through k.
  • The proof template — fractional packing via harmonic weights, LYM-based spread control, and rainbow matching for integrality — may apply to other prescribed-difference packing problems where sets become more rigid as a parameter grows.
  • The gap between the bound M_k(n) ≤ n⌈(1+ε)k⌉ and the lower bound nk means there is at most nεk wasted positions; finding an explicit sublinear slack function f_n(k) = o(k) with M_k(n) ≤ nk + f_n(k) remains open.

Reading between the lines

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

  • The dependence on the Delcourt–Postle rainbow matching theorem means the result inherits whatever quantitative bounds that theorem provides; improvements to the matching theorem's threshold constants would directly tighten the k_0(n,ε) threshold here.
  • The harmonic identity E[N_d] = L/(kd) is the structural keystone: it is what makes the fractional load uniform. Any other packing problem where a similar harmonic or 1/d-weighted partition can be constructed might admit the same proof strategy.
  • The proof is asymptotic in an essential way — it maintains slack during the matching step and removes it only as k → ∞, so the method is unlikely to resolve exact tiling questions without a fundamentally different rounding argument.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper proves that $M_k(n) = (1+o(1))nk$ as $k$ tends to infinity for every fixed positive integer $n$, confirming a conjecture of Alon, Dębski, Grytczuk, and Przybyło. Here $M_k(n)$ is the minimum interval length needed to pack translates of $B_d = {d, 2d, ..., nd}$ for $d = 1, ..., k$. The proof proceeds in three stages: (1) a random partition of an integer $L$ (Lemma 2.2) with harmonic expected part sizes, combined with a random ordering and the LYM inequality (Lemma 2.4), yields a fractional packing with uniform load and bounded per-difference concentration (Proposition 2.5); (2) this fractional structure is lifted to translates of $B_d$ in $[nL]$ (Proposition 3.1); (3) a random selection of $T = Theta(log^4 k)$ translates per difference produces an $n$-uniform edge-colored multi-hypergraph satisfying the hypotheses of the Delcourt–Postle rainbow matching theorem (Theorem 2.1), which then yields an integral packing (Lemma 4.1, Theorem 1.2).

Significance. The result resolves a stated conjecture and improves the previous upper bound of $3nk$ to the asymptotically optimal $(1+o(1))nk$. The proof is self-contained up to the Delcourt–Postle theorem, which is applied with explicitly verified hypotheses. The random partition construction (Lemma 2.2) is parameter-free and the probabilistic estimates in Lemma 4.1 carry polynomial slack in $log k$. The fractional-to-integral reduction via rainbow matchings is clean and well-motivated.

minor comments (5)
  1. Lemma 2.2: The inductive construction is well-founded, but the reader must verify that recursive calls have first argument strictly between $k$ and $L$. Adding one sentence stating this explicitly would improve clarity.
  2. Proposition 2.5, proof of (2.6): The bound $d E N_d / (c_0 log k) + O(k^{-1/4})$ uses $E N_d = L/(kd)$ and $L le 2k$, giving $le 2/(c_0 log k)$. This is correct, but the constant $C$ should be noted as depending on $c_0$.
  3. Lemma 4.1: The exponent $7/8$ and the threshold $D^{7/8}$ are stated without special significance. A brief remark that $D^{7/8} gg log^3 k$ (the relevant mean) would help the reader see the slack at a glance.
  4. Reference [1] (Alon et al.) and reference [4] (Delcourt–Postle) are both cited as arXiv preprints. If published versions exist, they should be updated.
  5. The abstract and introduction use $epsilon$ and $varepsilon$ interchangeably; standardizing to one form would be cleaner.

Simulated Author's Rebuttal

0 responses · 0 unresolved

The referee report is positive, recommending acceptance with no major comments. The referee's summary of the paper is accurate and detailed. We thank the referee for the careful reading and confirm that the summary correctly describes the three-stage proof structure, the role of each lemma, and the application of the Delcourt–Postle rainbow matching theorem.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation is self-contained against external benchmarks

full rationale

I traced the full derivation chain from the trivial lower bound M_k(n) >= nk (Eq. 1.1) through Theorem 1.2. The lower bound is a counting argument. The upper bound construction is parameter-free: Lemma 2.2's random partition depends only on L and k (using uniform permutations and induction), with E[N_d] = L/(kd) derived from standard cycle-count expectations, not fitted to the target. The weights q_{d,s} = (k/L)Q_{d,s} are determined by the construction, not by the conjecture. Proposition 2.5's three properties (2.4)-(2.6) follow from Lemma 2.2, Lemma 2.3 (Markov + generating function), and Lemma 2.4 (LYM inequality), all standard tools. Proposition 3.1 converts interval weights to arithmetic-progression translates using the identity (3.2), with the codegree bound following from |u-v| = jd determining at most n-1 values of d. Lemma 4.1's random sampling uses Chernoff bounds (2.1)-(2.2) with union bounds over O(k^2) events, all having polynomial slack in log k. The final step invokes the Delcourt-Postle rainbow matching theorem (Theorem 2.1, ref [4]) by externally verified authors, with all four hypotheses explicitly checked. No parameter is fitted to a subset of data and then 'predicted' on related data. No self-citation is load-bearing: the only self-referenced elements are standard tools (Chernoff, LYM, Markov). The Delcourt-Postle theorem is an independent external result. The construction does not smuggle in the target M_k(n) = (1+o(1))nk by definition or ansatz.

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

No free parameters are fitted or tuned. No new mathematical entities are postulated. The proof uses standard tools (Chernoff bounds, LYM inequality, random permutations) and one recent external theorem (Delcourt–Postle rainbow matching). The constants C and c₀ arise from the construction and are not fitted to data.

assumptions (4)
  • domain assumption Delcourt–Postle rainbow matching theorem (Theorem 2.1 [4]): for r-bounded edge-colored multi-hypergraphs with bounded degree, sufficient color class size, bounded codegree, and bounded color-degree, a full rainbow matching exists.
    Invoked in the proof of Theorem 1.2 (Section 4) to convert the fractional packing into an integral packing. This is the single load-bearing external result.
  • standard math Chernoff bounds for sums of independent Bernoulli variables (equations 2.1, 2.2).
    Used in Lemma 4.1 to control vertex degrees, color-degrees, and pair-codegrees via union bounds.
  • standard math LYM inequality for antichains in the Boolean lattice (equation 2.3).
    Used in Lemma 2.4 to bound the probability that a randomly ordered block covers a fixed point.
  • standard math Standard properties of uniform random permutations on [L], including cycle-count generating functions and expected cycle counts.
    Used in Lemma 2.2 (random partition construction) and Lemma 2.3 (lower-tail estimate for cycle count).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Solution to a conjecture of Alon, D\k{e}bski, Grytczuk and Przyby\l{}o on fixed-cardinality arithmetic progressions." pith.science (2026). https://pith.science/paper/CXUXZXFB

@misc{pith2026260706113,
  author       = {Pith},
  title        = {Pith review of: Solution to a conjecture of Alon, D\kebski, Grytczuk and Przyby\lo on fixed-cardinality arithmetic progressions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CXUXZXFB}},
  note         = {Machine review of arXiv:2607.06113}
}
abstract

Fix a positive integer $n$, and put $B_d=\{d,2d,\ldots,nd\}$. Let $M_k(n)$ be the least integer $m$ for which one translate of each of $B_1,\ldots,B_k$ can be placed pairwise disjointly in $[m]$. We prove that, for every $\eps\in(0,1)$ and all sufficiently large $k$, one has $M_k(n)\le n\lceil(1+\eps)k\rceil$. Since the trivial counting bound gives $M_k(n)\ge nk$, it follows that $M_k(n)=(1+o(1))nk$ for every fixed $n$. This confirms a conjecture of Alon, D\k{e}bski, Grytczuk and Przyby\l{}o on prescribed-difference packings of fixed-cardinality arithmetic progressions.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    N. Alon, M. Dębski, J. Grytczuk and J. Przybyło, Packing arithmetic progressions, arXiv:2603.02786[math.CO], 2026

    work page arXiv 2026

  2. [2]

    Alon and J

    N. Alon and J. H. Spencer,The Probabilistic Method, 4th ed., Wiley, Hoboken, 2016

    work page 2016

  3. [3]

    Amiot, Structures, algorithms, and algebraic tools for rhythmic canons,Perspectives of New Music49(2) (2011), 93–142

    E. Amiot, Structures, algorithms, and algebraic tools for rhythmic canons,Perspectives of New Music49(2) (2011), 93–142

    work page 2011

  4. [4]

    Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings

    M. Delcourt and L. Postle, Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings,arXiv:2204.08981v3[math.CO], 2024

    work page Pith review arXiv 2024

  5. [5]

    Frankl and V

    P. Frankl and V. Rödl, Near perfect coverings in graphs and hypergraphs,European J. Combin. 6 (1985), 317–326

    work page 1985

  6. [6]

    Johnson, Perfect rhythmic tilings, lecture at the MaMuX seminar, IRCAM, 2004

    T. Johnson, Perfect rhythmic tilings, lecture at the MaMuX seminar, IRCAM, 2004

    work page 2004

  7. [7]

    Lubell, A short proof of Sperner’s lemma,J

    D. Lubell, A short proof of Sperner’s lemma,J. Combin. Theory1 (1966), 299. 9

    work page 1966

  8. [8]

    E. S. O’Keefe, Verification of a conjecture of Th. Skolem,Math. Scand.9 (1961), 80–82

    work page 1961

Show all 11 references
  1. [9]

    Pippenger and J

    N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs,J. Combin. Theory Ser. A51(1) (1989), 24–42

    1989

  2. [10]

    Rödl, On a packing and covering problem,European J

    V. Rödl, On a packing and covering problem,European J. Combin.6(1) (1985), 69–78

    1985

  3. [11]

    Skolem, On certain distributions of integers in pairs with given differences,Math

    Th. Skolem, On certain distributions of integers in pairs with given differences,Math. Scand.5 (1957), 57–68. 10

    1957

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.