For a fixed array, pair (g,h) has C_gh=binom(N_gh,d_gh) possible subsets. Here binom(N,d)=N!/(d!(N-d)!) counts size-d subsets, with 0!=1. Join test-group vertex g to variable-group vertex h with b_gh=ceil(log2 C_gh) ordered parallel wires. Their bits index zero through 2^b_gh-1; both endpoint tensors decode the SAME index. Values at least C_gh are invalid and give entry zero. If C_gh=1, use no wires and take the unique subset, even when it is the entire incidence set. For N_gh=3,d_gh=1, two wires encode three singleton subsets; the fourth bit string must not add an extra contribution.

Encoding a fixed-size incidence subset with binary wires

For each pair (g,h), let d_gh be the number of selected incidences in the monomial. Enumerate integer arrays with 0<=d_gh<=N_gh and sum d_gh<=K. There are at most (K+1)^(J^2)=2^{O_(k,c)(sqrt(n) log n)} arrays. This is an upper bound: many counter settings violate the restrictions and are skipped. Store J^2 counters and process one array at a time. Every squarefree incidence monomial of degree at most K belongs to exactly one such array, obtained by counting its selected coordinates in each group pair. Including coordinates of zero-coefficient monomials is harmless; their eventual tensor weight is zero.

AI Agents

Put lambda=ceil(log2 n), nu=ceil(log2 lambda), and J=ceil(n^(1/4)). Partition the remaining tests and the free variables separately into J groups with sizes differing by at most one; empty groups are allowed. Let N_gh count distinct incidences from test group g to variable group h, and N=sum N_gh. A test scope has polylogarithmic size and each free variable has polylogarithmic incidence after branching. Each group contains O_c(n^(3/4)) objects, so its total incident coordinates are at most n^(3/4) lambda^{O_(k,c)(1)}. Grouping is not yet an assignment of bits to variables.

Grouping tests and variables before indexing incidence subsets

Let a<=cn be the remaining tests, each of degree at most k, and ell=n+1. In test i the V^j coefficient has incidence degree at most k(1+2j); replacing positive powers by first powers cannot increase degree. Test incidence names are disjoint, so their product is multilinear in all incidence coordinates. Shared truncation keeps only sum_i j_i<=ell-1. Therefore every surviving incidence monomial uses at most K=k(a+2(ell-1))=O_(k,c)(n) distinct coordinates. It may use two different copies of the same original variable; those are distinct incidences until the final Boolean substitution.

Why retained incidence monomials have only linearly many selected coordinates

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