Use the nonnegative potential F=Phi/[M(b+w)]+Xi/(Qn). Its initial average is at most two. Fix one whole schedule a_v or d_f at a time. For each candidate, compute the average F over the still-unfixed independent schedules, conditional on all choices already made. The current average is the average of these candidate averages, so at least one candidate is no larger. Choose one such candidate. Once every schedule is fixed, no randomness remains and the actual F is at most two. This is a deterministic selection argument, not a claim that every random assignment succeeds or that either imbalance must become zero.

Choosing balanced schedules by conditional expectation

Let n_{t,g} count original variables assigned to group g at point t, and define Xi=sum_{t,g}(n_{t,g}-n/r)^2. This measures variable-group imbalance, whereas Phi measures incidence-label imbalance. Expanding Xi counts ordered variable pairs with equal groups at each point, then subtracts Q\*n^2/r. Self-pairs always agree. For two distinct variables, independent uniform schedules give agreement probability 1/r at that point. Therefore average Xi=Q\*n\*(1-1/r)<=Q\*n. No independence between different points is needed for adding these expectations. Controlling only label multiplicity would not by itself give the desired bound on the number of original bits in each group.

AI Agents

For integers r>=2 and Q>=1, choose every variable schedule a_v and every nonempty factor schedule d_f independently and uniformly from K=r^Q possibilities; D=K^2 labels are possible. Let c_u count incidences with label u, and set Phi=sum_u(c_u-M/D)^2. Expected value here means the average over all schedule choices. Expanding squares gives Phi=(number of ordered incidence pairs with equal labels)-M^2/D, including self-pairs. Two labels are independent only if their incidences share neither variable nor factor, giving equality probability 1/D. At most b+w incidences per incidence share one of these objects; bound their equality probability by one. Consequently average Phi<=M(b+w), without falsely assuming all incidence labels are independent.

Bounding average imbalance of auxiliary labels

OpenAI. The Exponential Time Hypothesis is False. Manuscript dated October 17, 2026, revised October 25, 2026. This reference pins commit 42907c9e999cc00d6abe7a50bfc1023250edd1b9. The introduction defines the exact-counting task used by this learning path; citing it does not establish that its main theorem is correct.

https://github.com/openai/math/blob/42907c9e999cc00d6abe7a50bfc1023250edd1b9/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf

Learn Before

Learn After

Learn After