REVIEW 1 major objections 2 references
An exact small-$n$ computation of the minimum 2-coloring discrepancy of $K_n^{(3)}$
T0 review · 1 major / 0 minor · reviewed 2026-07-01 · grok-4.3
Pith's one-line read The minimum 2-coloring discrepancy δ₂(n) equals min_x |x(n-x)/2 - n(n-1)/12| for n up to 21.
desk verdict Exact δ₂(n) for n=7 and 9 via full enumeration over STSs and colorings, matching the GGS formula; larger n rest on simulated annealing with no optimality certificate. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The GGS Example 1.1 family of 2-colorings optimized over the parameter x, which produces the discrepancy value given by that absolute difference formula.
What would settle it
Discovery of any 2-coloring for n=13,15,19 or 21 whose maximum discrepancy over all STSs is strictly smaller than the formula's value would falsify the exact match.
Extended reading notes
Core claim
For n in {7,9,13,15,19,21} with n ≡1 or 3 mod 6, the minimum 2-coloring discrepancy δ₂(n) of K_n^{(3)} equals the minimum over integer x between 0 and n of the absolute value |x(n-x)/2 - n(n-1)/12|, achieved by optimizing the GGS Example 1.1 family of colorings.
Load-bearing premise
That the simulated annealing searches locate a globally optimal coloring for n from 13 to 21.
Editorial extensions
If this is right
- For n=7 and 9 the equality is proven by exhaustive enumeration of all labelled STSs and colorings.
- For the larger n the equality holds according to simulated annealing searches.
- At n=9 every optimal coloring has a wide basin of nearby colorings that also achieve discrepancy 1.
- Random 2-colorings have average maximum discrepancy growing linearly as roughly n / sqrt(12) times sqrt(log K).
- The typical discrepancy is much smaller than the worst-case Omega(n^2) bound from prior work.
Reading between the lines
- If the conjectured formula holds for all n, then δ₂(n) is at most about n/4.
- Simulated annealing may be sufficient to find global minima in this discrepancy problem for moderate n.
- Similar computational approaches could be used to test the formula for the next few n beyond 21.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper computes the 2-coloring discrepancy δ₂(n) for Steiner triple systems on K_n^{(3)} for n ∈ {7,9,13,15,19,21} (n ≡ 1,3 mod 6). It reports that these values exactly match the minimum over the GGS Example 1.1 family, i.e., δ₂(n) = min_{x∈[0,n]∩ℤ} |x(n-x)/2 - n(n-1)/12|. The values are obtained by exhaustive enumeration over all labelled STSs (30 for n=7, 840 for n=9) and all 2-colorings for the two smallest cases, and by simulated annealing for the remaining cases. The manuscript also reports random-coloring statistics for r=2,3,4 and states a conjectural closed-form formula for general n.
Significance. The exhaustive enumeration for n=7 and n=9 rigorously verifies that the GGS family achieves the minimum discrepancy in those cases; this is a clear strength because the searches are independent of the formula and the enumeration is complete. The simulated-annealing results supply supporting evidence for the conjecture but do not prove optimality. The random-coloring statistics usefully contrast typical-case linear growth with the known worst-case Ω(n²) lower bounds.
major comments (1)
- [Abstract] Abstract: the claim of 'an exact value of δ₂(n) for each such n' (including n=13,15,19,21) is load-bearing for the title and main result, yet the values for these n rest on simulated annealing locating a coloring whose discrepancy equals the GGS formula. Simulated annealing supplies no certificate that a lower-discrepancy coloring was not missed, so the reported figures are only upper bounds; if any better coloring exists the exact-match claim fails.
Simulated Author's Rebuttal
We thank the referee for the careful review and for highlighting the important distinction between rigorous and computational results. We address the major comment below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [Abstract] Abstract: the claim of 'an exact value of δ₂(n) for each such n' (including n=13,15,19,21) is load-bearing for the title and main result, yet the values for these n rest on simulated annealing locating a coloring whose discrepancy equals the GGS formula. Simulated annealing supplies no certificate that a lower-discrepancy coloring was not missed, so the reported figures are only upper bounds; if any better coloring exists the exact-match claim fails.
Authors: We agree that simulated annealing yields only an upper bound on δ₂(n) and supplies no optimality certificate. The manuscript already distinguishes exhaustive verification (n=7,9) from simulated-annealing search (n=13,15,19,21), but the abstract's opening phrasing can be read as claiming rigorous exactness for all listed n. We will revise the abstract to state explicitly that exact values are obtained for n=7 and n=9 via exhaustive enumeration, while for the remaining n we computationally achieve the GGS formula value (supporting the conjecture) without claiming a proof of minimality. The title and main computational contributions will be adjusted for consistency with this clarification. revision: yes
Circularity Check
No circularity; independent exhaustive and SA searches verify external GGS-derived formula
full rationale
The paper reports exact δ₂(n) values for n in {7,9,13,15,19,21} that match the closed-form min obtained by optimizing the GGS Example 1.1 family. For n=7,9 this rests on exhaustive enumeration over all labelled STSs and 2-colourings, which is an independent verification. For the remaining n it rests on SA searches that locate colourings attaining the formula value. Neither case reduces the claimed minimum to the formula by construction, self-definition, or fitted-input renaming; the searches operate directly on colourings of the STSs. The formula itself is imported from the external GGS citation rather than any self-citation chain. The paper explicitly labels the general closed-form statement a conjecture. No load-bearing step therefore collapses to its own inputs.
Assumptions & free parameters
assumptions (1)
- standard math Steiner triple systems exist precisely when n ≡ 1 or 3 mod 6
Cite this review
Pith. "Pith review of An exact small-$n$ computation of the minimum 2-coloring discrepancy of $K_n^{(3)}$." pith.science (2026). https://pith.science/paper/WRLXL3AX
@misc{pith2026260500492,
author = {Pith},
title = {Pith review of: An exact small-$n$ computation of the minimum 2-coloring discrepancy of $K_n^(3)$},
year = {2026},
howpublished = {\url{https://pith.science/paper/WRLXL3AX}},
note = {Machine review of arXiv:2605.00492}
}
abstract
For an integer $r \ge 2$ and an order $n \equiv 1, 3 \pmod{6}$, write $\delta_r(n)$ for the minimum, over all $r$-colourings $\chi : \binom{[n]}{3} \to [r]$, of $\max_{\mathcal{S}} \mathrm{disc}(\mathcal{S}, \chi)$, where the maximum is over labelled Steiner triple systems $\mathcal{S}$ of order $n$ and $\mathrm{disc}(\mathcal{S}, \chi) = \max_c |\#\{T \in \mathcal{S} : \chi(T) = c\} - |\mathcal{S}|/r|$. Following Gishboliner, Glock, and Sgueglia \cite{GishbolinerGlockSgueglia2025}, the bulk of the recent work on this quantity has been on lower bounds for $r \ge 3$ (proving $\delta_r(n) = \Omega(n^2)$) and on structural characterisation of the low-discrepancy 2-colourings. We give three small computational contributions in the small-$n$ regime $n \in \{7, 9, 13, 15, 19, 21\}$: An exact value of $\delta_2(n)$ for each such $n$, matching the formula $\delta_2(n) = \min_{x \in [0, n] \cap \mathbb{Z}} |x(n-x)/2 - n(n-1)/12|$ obtained by optimising the GGS Example 1.1 family. Rigorous for $n \in \{7, 9\}$ via exhaustive search over labelled STSs ($30$ resp. $840$ systems) and over all $2$-colourings; computational for $n \in \{13, 15, 19, 21\}$ by simulated-annealing search; A wide near-optimal basin: at $n = 9$, every two-colour-flip neighbour of the optimal Example~1.1 colouring that maintains discrepancy $1.0$ exists; about $34\%$ of two-flip perturbations preserve optimality; Random-colouring statistics for $r \in \{2, 3, 4\}$: $\langle\max_{\mathcal{S}}\mathrm{disc}\rangle$ grows linearly in $n$, in agreement with a heuristic Gaussian estimate $n / \sqrt{6r} \cdot \sqrt{2 \log K}$ over $K$ sampled labellings; the typical-case discrepancy is far below the GGS worst-case $\Omega(n^2)$. We additionally state a conjectural exact formula for $\delta_2(n)$ that holds for every $n \equiv 1, 3 \pmod{6}$.
Reference graph
Works this paper leans on
-
[1]
L. Gishboliner, S. Glock, and A. Sgueglia,Steiner triple systems with high discrepancy,arXiv:2503.23252, 2025;J. Combin. Designs(2026)
-
[2]
M. Kwan, A. Sah, M. Sawhney, and M. Simkin,Almost all Steiner triple systems have perfect matchings, Ann. of Math.(2) (2024) and earlier preprints. Email address:mrnt0810@gmail.com
work page 2024
Reviewed July 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.