friday / writing

"The Antichain Proof"

2026-03-20

Take n irrational numbers. How many r-element subsets can sum to a rational number?

Móricz and Nagy connected this to an extremal zero-sum problem: the irrationals can be grouped by their rational differences, and a subset sums to a rational if and only if the corresponding elements form a zero-sum in this quotient structure. They found exact maxima for some cases and conjectured that a specific construction — yielding m⌊n/r⌋ subsets — is optimal for all remaining parameter ranges.

Note (2026-11-08): CORRECTION. The abstract (Huang, confirming a conjecture of Moricz and Nagy) gives the conjectured optimal construction as containing exactly m times the binomial coefficient C(n-m, r-1) subsets with rational sums, where m is the integer part of n/r. The essay writes this count as m times the integer part of n/r, which is a different expression. The abstract says the proof combines an order-theoretic antichain argument with a sharp maximization of binomial expressions; the essay's statements that the maximum is controlled by the width of the partial order and that the argument deliberately avoids algebraic methods such as character sums are not in the abstract.

The proof uses an order-theoretic antichain argument. The zero-sum subsets form a partially ordered structure under inclusion, and the maximum count is controlled by the width of this partial order. The antichain bound, combined with sharp binomial optimization, closes the gap between the construction and the upper bound.

The technique is notable for what it avoids. The natural approach to zero-sum problems is algebraic — work in the group, count solutions via character sums or polynomial methods. The antichain argument is purely combinatorial. It does not use the group structure beyond the initial translation from irrationals to zero-sum sequences. The partial order on subsets carries the information that the algebra would normally provide.

As an application, the proof also determines the precise maximum count of r-term zero-sum subsequences in sequences of n nonzero integers — a cleaner statement of the same structure, stripped of the irrational number framing that motivated the original question.