Research program

Selfridge integer complexity

This program attacks Selfridge's question $\lVert2^n\rVert=2n$ by preserving the actual cost of factored formulas and turning restricted expression shapes into exponential Diophantine equations. Its present results close several infinite branches of a normalized three-addition family. The unrestricted problem remains open.

Status. Paused at a structural boundary after a sustained attack. The scoped claims have self-contained public statements and reproducible evidence. They include a cyclotomic ladder, the odd-exponent branch, the exceptional even $x=4$ lift, three complete positive-type-I exterior layers, a uniform obstruction for every higher layer, the complete complementary third layer, and a complete classification of the complementary $a\ge1$ tower. The former 21-row frontier now contains exactly ten harmless controls. In the $a=0<g$ orientation, the three surviving $f=1$ rows now share an exact 3-adic valuation law because all cancelling tied-minimum strata have been excluded. The remaining $f=2$ split now has an analogous universal law after all ten possible cancelling strata are excluded. The first two least-ternary-exponent layers are now completely classified: exactly seventeen proper controls remain, every one costing at least $2N+6$ . The classical S-unit theorem now proves that all eight normalized complementary factor shapes have only finitely many presentations, though it supplies no height cutoff. In the reopened $f=0$ branch, forty canonical placements leave twenty possible tied-minimum cancellations. All twenty are now completely classified. The exceptional locus consists of two harmless controls, with displayed excesses four and thirteen, and every other solution obeys a universal 3-adic valuation law. The obvious next-digit continuation branches rather than closing the nonexceptional remainder, so further work requires a new structural reduction rather than another minimum layer. No external review or novelty determination is recorded. These results live in the Lab's ordinary research architecture; none is a separate Publication or a solution of Selfridge's problem.

Driving question

Where could a saving over repeated twos hide?

The obvious expression for $2^n$ uses $2n$ ones. Any saving must come from addition creating a useful nonsmooth factor more cheaply than multiplication by twos would. The present attack freezes a substantial three-addition architecture,

M\bigl[A(B+C)(D+E)+F\bigr],

and keeps every displayed atom and unit charge. This makes the cost comparison exact while exposing congruences, valuations, multiplicative orders, primitive divisors, and p-adic lifting.

Completed branch structure

What the attack has actually established

Primitive proper forks have opposite mod-eight characters and final 2-adic exponent at most two.
The entire y=0 cyclotomic ladder has no nonsmooth rung beyond the known harmless controls.
The complete odd-exponent branch has one genuine solution, $7\cdot73+1=2^9$ , but its factored presentations cost more than $2N$ .
At the first even layer, most canonical shapes are excluded. The apparent 3-adic lift of $15\cdot17+1=2^8$ is now completely contradicted by its first Hensel digit and a nine-residue table modulo 19441.
The complete first-layer type-II2 family is empty. A mod-seven divisibility gate, a mod-73 boundary certificate, and exact quotients modulo 19441, 6481, and 13 eliminate every large- $x$ class, including both imbalances and the diagonal.
The last type-II1 family falls to a modulus-7 gate followed by a disjoint modulus-13 residue pair. Consequently the full $a=1$ layer of the active canonical branch is closed.
The first serious $a=2$ type-I2 family is also empty. A 3-adic lift removes the formal rational boundary, after which modulo 271 gives a complete residue separation.
The final odd-exponent type-II2 family falls to coupled quotients modulo 73 and 577. Consequently the full $a=2$ layer is closed.
At $a=3$ , the exact entry table and finite gate quotients first isolate the remote tail; a modulus-262657 quotient followed by moduli 7 and 13 closes every remaining row.
A paired-prime obstruction modulo 73 and 262657 excludes every exterior layer $a\ge4$ for both canonical positive-factor types. Together with the lower layers, this completes the entire $g=0$ positive-type-I branch.
For the complementary factor $2^x+3^y$ , a complete 524,288-state quotient closes the $a=3$ layer. A coupled-order quotient then proves $x\le10$ for every remaining low-layer solution.
The 21 complementary low-layer rows are now classified. The full valuation $N=v_2(F(v,y))$ fixes eleven rows and turns each other row into a one-dimensional Hensel graph. At precision $2^{22}$ , all 20,480 graph states fail modulo 65,537.
Exactly ten positive-type-II controls remain, representing four factorizations at $N=8,10,12$ . Every one costs at least $2N+4$ . The earlier five-row height barrier remains correct but is superseded by this complete nonboundary exclusion.
In the complementary $a=0<g$ orientation, quadratic reciprocity reduces twelve canonical residue pairings to six. It also excludes the complete $f=2$ subbranch where both inner sums contribute one factor of two.
In the three surviving complementary $f=1$ rows, canonical parity leaves six possible tied-minimum cancellations. Their complete residue periods modulo 7 and 73 are disjoint, so every solution satisfies $\min(b,y,g)=1+v_3(K+1-h)$ .
In the alternative complementary $f=2$ split, the valuation-two odd part has four residue types and leaves eight gate placements. Ten possible tied-minimum cancellations are eliminated by complete periods modulo 7, 73, 487, and 2593. Every solution therefore satisfies $\min(b,y,g)=1+v_3(K+2-h)$ .
Combining the two valuation laws at $m=1,2$ produces 32 exact minimum strata. Nine are empty; the others reduce to 40 periodic lift graphs with common period $20{,}652{,}025{,}680$ . Their centered roots are seventeen harmless proper presentations and nine improper rational identities, so every noncontrol proper solution has output exponent at least the common period.
The next ternary digit modulo 729 eliminates all eleven boundary-rooted graphs and freezes 26 control-rooted graphs. The last three graphs reduce to two exponential equations; Matveev's explicit logarithmic bound and exact modular descent leave only the seventeen centered controls. Thus the complete $m=1,2$ layers contain no cost-saving presentation.
Expanding every complementary equation gives five positive S-units in a multiplicative group of rank at most six. Evertse–Schlickewei–Schmidt therefore proves uniform finiteness of all eight fixed factor shapes, with the crude bound $8\exp(7\cdot30^{15})$ . The theorem counts solutions but does not bound their heights.
In the complementary $f=0$ branch, the reciprocity table has forty canonical placements and twenty possible tied-minimum cancellations. Exactly two have all three ternary exponents tied. Complete mod-7/mod-73 tables eliminate one; a 2-adic gate and a factorization of 65 show that the other contains only $(2+3)(1+8\cdot3)+3=2^7$ , costing four extra ones.
The eighteen pair-minimum cancellation strata reduce under a complete four-prime quotient to 23 states. Modulo 27 leaves one family, and an elementary factorization of 175 proves its only solution is $(4+3)(1+8\cdot3)+3^4=2^8$ , costing thirteen extra ones. Thus all twenty exceptional cancellations are classified, and every other $f=0$ solution satisfies $\min(v,y,g)=1+v_3(K-r-u)$ .

Read the exact theorems, proofs, boundaries, and evidence →

Structural stopping boundary

The residue-table phase is complete; a different idea is now required

After removing the final common power of two, the complementary orientation is

RS+3^g=2^K.

The uniform S-unit theorem proves finiteness but gives no effective height cutoff. The new theorem removes every exceptional first-digit cancellation in $f=0$ , yet a direct lift of the forty general placements to modulo 729 still leaves 1,953 patterns after the valuation law is imposed. The unresolved work is therefore not a short finite tail. Reopening this program should require an effective reduction of the product-structured six-term S-unit equation, a uniform dominance or freezing theorem, or a normal-form theorem connecting arbitrary formulas to this restricted grammar.

Research discipline

Restricted theorems remain restricted

The program uses complete residue periods rather than large finite searches whenever it claims an infinite exclusion. Bounded computations serve as transcription checks and positive controls. Imported theorems are named at the exact boundaries where they are used. A result enters the ordinary research site when it is mathematically useful; only a resolution or genuinely substantial advance would warrant a separate publication.