FLATTEN — the least height flattened to a given depth
The object: an integer vector c of width M read as the polynomial P(x) = Σ c_i x^i of degree < M. Its flattening is the multiplicity of the root 1, P is flattened to J when that is at least J, its height is max |c_i|, and h(M, J) is the least height of a nonzero P of width M flattened to depth J. A cell is a pair (M, J) with J < M. The vectors flattened to J are (x − 1)^J·Z[x] cut at degree < M, a lattice of rank r = M − J, so h is the least sup norm of a nonzero vector. The pure products are ∏(x^{g_i} − 1) over a multiset of positive parts g_i; one is admissible at a cell when its degree Σg_i is below M and its part count reaches J, and ph(M, J) is the least height of an admissible one, so h ≤ ph and a cell fails when h < ph. The chart is h over M = 4…40, J = 2…min(30, M − 1), 695 cells, and the corner the 63 cells M = 4…12, J = 1…M − 1, which take in J = 1, where the chart does not reach. The inverse dial d_k(J) is the least degree of a nonzero multiple of (x − 1)^J of height at most k, so h(M, J) ≤ k exactly when M > d_k(J). The verifiers are flatten.py, members.py, band.py and rank2.py.
The thesis: forcing a polynomial to vanish deeply at 1 forces its coefficients up, and the cheapest way to pay is a product of factors x^g − 1 in the corner, as computed, and at ranks 1 and 2 by proof, while on the chart past the corner such a product with some of its cyclotomic factors traded for reciprocal factors that are not cyclotomic wins at 83 cells, more often the deeper the flattening. Read one rank at a time the wins sit in a band of depths, past which, at ranks 5 to 10 as far as the scans reach, a pure product attains the least height again. Read backwards, the same numbers are the shortest integer-tap filters that annihilate every polynomial signal of a given degree: one function read two ways, so a chart failure is a break of the products there, as at taps bounded by 9 and depth 10, and the filters alone show two more, at taps bounded by 8 and 11 and depth 15.
flatten.py is a tool in its own right: for any cell within its node budget it returns h(M, J) with a witness, by an integral lattice reduction and a sup-norm enumeration whose radius is proved sufficient, run in floating point with a relative slack, every witness rechecked in integers and its minimality resting on that slack, reading the whole chart in under three seconds in pure Python (flatten.py::least_height, the chart's run flatten.py::stage_chart).
Flattening is annihilation
Tier: property (proved).
Verifier: proof.
Write P(x) = Σ_j m_j (x − 1)^j, so m_j = Σ_i C(i, j) c_i. The vector is flattened to J exactly when m_j = 0 for every j < J, and since the binomials C(i, j) and the powers i^j with j < J span the same polynomials in i, that is exactly Σ_i c_i i^j = 0 for every j < J. Read as filter taps, c sends a signal s to Σ_i c_i s(n − i), and it annihilates every polynomial signal of degree < J exactly when it is flattened to J. So d_k(J) + 1 is the least number of taps of such a filter with integer taps bounded by k in absolute value, and at k = 2 every tap is 0, ±1 or ±2, a sign and at most one binary shift.
The least height is a lattice minimum
Tier: property (the radius proved; that the floating-point enumeration
misses nothing rests on its slack and is not proved; the route agrees
with exhaustion at the 12 cells of width at most 6, and on whether
h = 1 at 33).
Verifier: proof; flatten.py::least_height, flatten.py::stage_chart.
Reduce the basis x^i (x − 1)^J, i < r, and let q be the reduced basis's own least height. A vector of sup norm at most q − 1 has Euclidean norm at most (q − 1)√M, so the Euclidean ball of that radius contains every lattice vector of height below q. Enumerate the ball, lowering q and shrinking the ball each time a lower height is met: what survives is h, with its witness. No product family enters the number it is compared against. The enumeration runs in floating point over Gram–Schmidt data that are exact integers, with a relative slack on the radius; that the slack loses no vector is not proved, so the minimum is exact as far as the enumeration is complete. Every vector it returns is rebuilt from integer coefficients and checked for height and for J exact divisions by x − 1. The whole chart and the J = 1 column over M = 4…40, 732 cells, close by this route; at every cell of width at most 6 the route agrees with an exhaustion of [−3, 3]^M, which decides h where h ≤ 3 and that h > 3 elsewhere, and at width at most 9 with an exhaustion of [−1, 1]^M on whether h = 1.
At rank 1 the least height is the central binomial
Tier: property (proved; read by the lattice route at all 28 rank-1
cells of the chart).
Verifier: proof; flatten.py::stage_chart.
At M = J + 1 the lattice is generated by (x − 1)^J alone, so h(J + 1, J) = C(J, ⌊J/2⌋), and a pure product with at least J parts and degree at most J has J parts, each 1, so it is (x − 1)^J itself and ph = h: a rank-1 cell cannot fail.
In the corner the least height is a pure product's
Tier: rule (exhaustive at the 63 corner cells, h read by the lattice
route, whose minimality rests on the enumeration's slack).
Verifier: flatten.py::stage_chart.
At every corner cell, h(M, J) = ph(M, J).
On the chart the products fail more often the deeper
Tier: rule (exhaustive over the 695 chart cells, h read by the lattice
route, whose minimality rests on the enumeration's slack).
Verifier: flatten.py::stage_chart.
h = ph at 612 cells and h < ph at 83. The failures sit at ranks 5 to 18 only, and they concentrate with the depth: 3 of 362 cells fail at J ≤ 12, 17 of 188 at J = 13…20 and 63 of 145 at J ≥ 21, so 0.8%, 9.0% and 43.4%. The bins mix ranks; over ranks 5 to 18 alone the ordering survives on the chart, 3 of 154, 17 of 112 and 63 of 104, so 1.9%, 15.2% and 60.6%, though at one rank the failures end with its band (below), and over the cells that can fail, those with ph > 1, 1.4% of 209, 9.0% of 188 and 43.4% of 145. The first failures by depth are h(23, 10) = 9 against 10, h(21, 12) = 39 against 44 and h(25, 12) = 25 against 28.
Through its table the inverse dial is a pure-product degree
Tier: rule (exhaustive at the 99 cells of the table and 15 cells past
it, each lattice verdict resting on the enumeration's slack).
Verifier: flatten.py::stage_dial.
At every cell of the table below, d_k(J) equals the least degree of a pure product of height at most k with exactly J parts, the pure law. Each cell is two computations sharing nothing: a walk over the multisets of J parts in nondecreasing order finds the least such degree δ, exact because multiplying by a factor x^(g_i) − 1 only negates the coefficients below index g_i, so those below the last part are final up to sign and a partial product with one above k is discarded; then the lattice at width δ decides that nothing of height at most k has lower degree. The same route finds the vector of height at most k one width up at all 115 cells it decides, the break d_8(15), where d_k(J) falls below the pure-product degree, among them, a check that it finds what exists. Rows J, columns k:
k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 1 1 1 1 1 1 1 1 1 2 3 2 2 2 2 2 2 2 3 6 4 3 3 3 3 3 3 4 11 7 5 5 5 4 4 4 5 15 11 8 8 6 6 6 6 6 22 16 11 10 9 9 9 9 7 30 22 17 14 14 11 11 11 8 41 26 20 19 18 16 15 15 9 48 34 27 22 22 21 20 19 10 61 45 33 29 27 23 23 23 11 69 51 43 34 30 30 25 25 12 · · · 44 38 36 32 31 13 · · · · 46 46 37 37 14 · · · · · · 49 47
Past the table the pure law holds at fifteen of the sixteen further cells the lattice decides, the sixteenth the break d_8(15) below: d_2(13) = 74 and d_2(15) = 95, d_3(12) = 52 and d_3(16) = 87, d_4 = 52, 60, 70, 78 at J = 13…16, d_5 = 55, 64, 71 at J = 14…16, d_6 = 52, 60 at J = 14, 15 and d_7 = 56, 64 at J = 15, 16. Thirteen cells at J ≤ 16 exceed the enumeration budget, among them the height-1 column past J = 11, where the least pure degrees 93, 112, 120, 141 and 159 at J = 12…16 are upper bounds only. The attaining multisets, one printed per cell at J = 6…11, follow no evident pattern: at k = 2 they open (1, 1, 2, 3, 4, 5) and at J = 8 repeat a part and skip one, (1, 1, 2, 3, 3, 4, 5, 7); at k = 3 they open (1, 1, 1, 2, 3, 3) and at J = 11 carry two unit parts, (1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8).
Read by rank, the failures sit in a band of depths
Tier: rule (ranks 1…22: ranks 1…4 to depth 140, ranks 5…10 to eight
depths past the last failure at each of which the champion attains h,
ranks 11…22 to the first).
Verifier: band.py::main.
Read one rank r = M − J at a time, ranks 1…22, as the depth grows past the chart, the chart's range of failing ranks 5…18 is where its width meets a band of failing depths, which the scans see end at ranks 5…10, and ranks 23 to 38, which the chart holds at shallow depths, are not scanned. Ranks 1…4 never fail at any depth to 140, width 144: that edge holds as far as the scan reaches, and at ranks 1 and 2 by proof. Ranks 19…22 fail first at J = 26, 23, 25 and 30, widths 43 to 52, just past the chart's 40: that edge is the chart's. The first failing depth J_lo(r) is ragged, 18, 22, 26, 19, 12, 24 at ranks 5…10. Inside a band depths with no failure can sit between failing ones: rank 5 fails at every depth from 18 to 30, rank 9 fails from 12 to 88 with seventeen depths among them where it does not, most below 36.
Past the last failure seen the champion attains the least height
Tier: rule (ranks 2…10 over the scanned depths; rank 2 is the theorem
below).
Verifier: band.py::main.
The champion at rank r is (1 + x)^(r−1)(x − 1)^J, from J = r − 1 on the pure product (x² − 1)^(r−1)(x − 1)^(J−r+1). At ranks 5…10 the last failing depth seen, J_hi, is 30, 33, 58, 60, 88 and 106, and from J_hi + 1 on the champion attains h at every depth scanned, including four read past each scan's stop; at ranks 2, 3 and 4 it attains h from J = 2, 7 and 13 through 140. The takeover depth J_ch, the least depth from which the champion attains h, exceeds J_hi by force, since the champion is a pure product and so cannot attain h where the products fail; what the scan adds is that no depth without a failure separates them: the depth after the last failure is where one closed form takes over from the whole family. A heuristic, carrying no tier, says why it should win eventually: the row of (x − 1)^J is a Gaussian of standard deviation about √J/2, each factor 1 + x differences it, cutting its height by a factor of order 1/√J, and the champion's cofactor (1 + x)^(r−1) is, up to a constant, the only one of degree below r with r − 1 of them. Nothing in the scan proves the band ends; each scan stops at J_hi + 8 and reads four depths past it.
A failing cell is a break on the dial
Tier: property (proved; the fence a rule on the dial's table, and the
heights read at the 83 failing cells).
Verifier: proof; members.py::stage_split; flatten.py::stage_dial.
If h(M, J) = k < ph(M, J), a vector of height k and degree below M is flattened to J, while every pure product of height at most k with at least J parts has degree at least M; so d_k(J) is below the least degree of a pure product of height at most k with exactly J parts, and the dial breaks at (k, J). The chart and the dial are one function read two ways, and the table's columns, unbroken through their last rows, fence the chart: d_k(J) never falls as J grows, since a multiple of (x − 1)^(J+1) is one of (x − 1)^J, and the last entry of every column of the table exceeds the chart's widths, so every cell the table leaves blank or passes has d_k(J) > 40 at k ≤ 8. A chart failure of height k ≤ 8 would be a break at (k, J) with d_k(J) < 40, and the table has none: the chart's failing cells have heights from 9 to 6,323,160.
At heights 8, 9 and 11 the dial breaks
Tier: rule (exhaustive at each cell: the witness exhibited, the lattice
empty one degree below, its emptiness resting on the enumeration's
slack).
Verifier: flatten.py::stage_break, members.py::stage_hunt.
d_8(15) = 55, while the least pure product of height at most 8 with fifteen parts has degree 56; the witness's cyclotomic part is the product with parts 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 7, of degree 45, times the degree-10 factor R = 2 + 3x + 3x² + 3x³ + 4x⁴ + 5x⁵ + 4x⁶ + 3x⁷ + 3x⁸ + 3x⁹ + 2x¹⁰. Nothing of height at most 8 flattened to 16 has degree below 56, so no product with more parts does better: a filter of 56 taps bounded by 8 annihilates every polynomial signal of degree below 15, and no product of factors x^g − 1 with taps bounded by 8 does it in fewer than 57. The columns k = 9…12, read from J = 1 under a node cap per decision, break twice more: d_9(10) = 22 against 23, the chart's first failure h(23, 10) = 9 with A = 2 + 4x + 5x² + 4x³ + 2x⁴ traded in, and d_11(15) = 48 against 49, with d_11(16) = 54, so no product with more parts does better, trading in N = 1 + x + 2x² + 3x³ + 3x⁴ + 3x⁵ + 2x⁶ + x⁷ + x⁸. Every other cell they decided obeys the pure law; from J = 17 (J = 18 at k = 11 and 12) to 20 the cap leaves them undecided, and none is read past 20.
A traded pure product attains every failing cell of the chart
Tier: rule (exhaustive over the 83 failing cells of the chart).
Verifier: members.py::stage_split, members.py::stage_swap.
Divide every cyclotomic factor out of the minimiser the route exhibits at each failing cell and what is left is never 1: it is B = 2 + 3x + 2x² at 51 cells, A = 2 + 4x + 5x² + 4x³ + 2x⁴ at 29, A·B at 2 and Q = 3 + 5x + 3x² at 1. Run forward, its seed A, B and Q read off these same minimisers, it is a construction with no lattice reduction in it: write an admissible pure product as (x − 1)^J times its cofactor, drop a block of the cofactor's cyclotomic factors, keeping (x − 1)^J, and bring in a product of A, B and Q of exactly the dropped degree. The least height over those swaps is h at all 83 cells, and never below h, since every swap is a lattice vector. A sham with the same degrees, heights and values at 1 but not reciprocal, 5 + 4x + 4x² + 2x³ + 2x⁴, 3 + 2x + 2x² and 5 + 3x + 3x², reaches h at none of them. The sham also moves the values at −1, to 5, 3 and 5 against 1, and, not reciprocal, cannot keep every root on the circle, so the run singles out neither reciprocity nor the circle.
The nine non-cyclotomic factors are reciprocal and need not sit on the circle
Tier: observation (nine factors); property for the family W_v and for
reversal.
Verifier: members.py::controls, members.py::stage_split,
members.py::stage_hunt, members.py::stage_deep.
Four of the five factors traded in at the chart's failures and the dial's breaks, A, B, Q and R, are irreducible, reciprocal, of leading coefficient 2 or 3, with every root on |z| = 1; the fifth, N, is not on the circle (below). Like the four are three non-cyclotomic factors of the minimisers the same route exhibits at the deeper widths 52 and 61, and a fourth, E below, at width 54 leaves the circle; of those four cells only (52, 30) is shown to fail, by the rank-22 scan: D = 3 + 9x + 15x² + 17x³ + 15x⁴ + 9x⁵ + 3x⁶ beside A at h(52, 30) = 42,222; F = 3 + 10x + 20x² + 29x³ + 33x⁴ + 29x⁵ + 20x⁶ + 10x⁷ + 3x⁸ beside A at h(61, 34) = 140,702; and G = 3 + 6x + 8x² + 6x³ + 3x⁴ alone at h(61, 33) = 67,323. By Kronecker's theorem (L. Kronecker, J. Reine Angew. Math. 53 (1857) 173–175), a monic integer polynomial with every root on the circle is a product of cyclotomic polynomials, so a non-cyclotomic factor on the circle cannot be monic, and there are infinitely many such factors: W_v = v + (2v − 1)x + vx², with B = W_2 and Q = W_3, is for every v ≥ 2 irreducible, its discriminant 1 − 4v being negative, not cyclotomic, being primitive with leading coefficient v, and has both roots on the circle: its trace polynomial, the S with W_v = xS(x + 1/x), is S(y) = vy + 2v − 1, whose root 1/v − 2 lies in [−2, 2], and a root y in [−2, 2] is a pair of roots z on the circle with z + 1/z = y. Two of the nine leave the circle: N, which is monic and not cyclotomic, its value 17 at 1 asking a factor Φ_(17^u), of degree at least 16, so off it by Kronecker, and E = 3 + 11x + 24x² + 37x³ + 43x⁴ + 37x⁵ + 24x⁶ + 11x⁷ + 3x⁸, alone at h(54, 32) = 108,376. What all nine share is reciprocity and positive coefficients. Reversal, P ↦ x^(M−1)P(1/x), maps the multiples of (x − 1)^J of degree below M onto themselves and keeps the height, so the minimisers at a cell are closed under reversal, and a minimiser unique up to sign is reciprocal up to sign, as is what is left of it once the cyclotomic factors are out; whether the route's minimisers are unique is not read. Eight take the value 1 at −1 and G takes 2, so that regularity is not the class's; the values at 1 run 7, 11, 17, 17, 26, 35, 71, 157, 193.
The height-1 column is classical
Tier: known.
Source: P. Borwein and M. J. Mossinghoff, "Polynomials with height 1
and prescribed vanishing at 1", Experiment. Math. 9 (2000) 425–433.
Borwein and Mossinghoff determine the least degree of a polynomial with coefficients in {−1, 0, 1} and a zero of order J at 1 for J ≤ 10, and compute every extremal polynomial; that least degree is d_1(J). The table's first column is the lattice's own decision at every depth to 11, and its values past 11 are not decided here.
Two free bounds
Tier: property (proved; how far each reaches, an observation over the
chart and the table).
Verifier: proof; flatten.py::stage_chart, flatten.py::stage_dial.
A ceiling. Over 0/1 vectors of width M the moment m_j takes values in 0…C(M, j + 1), so if 2^M > ∏_{j<J}(C(M, j + 1) + 1) two of them share their first J moments and their difference is a height-1 vector flattened to J: h(M, J) = 1. On the chart and the J = 1 column this reaches depth 1 at M ≤ 8, depth 2 at M = 9…23 and depth 3 at M = 24…40, and every cell it reaches has h = 1.
A floor. Let P have height at most k and degree at most T, flattened to J, and let ζ be a primitive p^u-th root of unity, p prime, with minimal polynomial Φ_{p^u} of degree φ(p^u) = (p − 1)p^(u−1). If Φ_{p^u} does not divide P, the norm of P(ζ) is a nonzero integer divisible by the norm of (ζ − 1)^J, which is p^J, while every conjugate of P(ζ) is at most k(T + 1) in size; so J log p > φ(p^u) log(k(T + 1)) forces Φ_{p^u} to divide P, and the forced factors and (x − 1)^J fit in degree T. The least T passing that test is a floor on d_k(J). It meets the table at 27 of the 99 cells, all at J ≤ 5, and falls away with the depth: 26 against 69 at k = 1, J = 11.
At rank 2 the least height is the row's largest step
Tier: theorem.
Verifier: proof; rank2.py::main.
The rank-2 lattice is {(a + bx)(x − 1)^J}. With β_i = C(J, i), zero outside 0 ≤ i ≤ J, its height is H(a, b) = max_i |a·β_i − b·β_{i−1}|. Let U = β_μ, μ = ⌊J/2⌋, the row's largest entry attained first at μ, and V = max_i |β_i − β_{i−1}|. For every J ≥ 2,
h(J + 2, J) = V, attained only at ±(1 + x)(x − 1)^J,
and the second minimum, the least height of a vector independent of that one, is U, attained at ±(1, 0) and ±(0, 1) and nowhere else. The proof: H(a, b) = H(−a, −b), and the row's palindrome gives H(a, b) = H(b, a). Every inner step |β_i − β_{i−1}| is below U since both entries are at least 1 and at most U, and the two end steps are 1, so V ≤ U − 1 once U ≥ 2, which is J ≥ 2. If a and b have opposite signs, the index μ pays |a|U + |b|β_{μ−1} > U; if one is zero, the index μ (or μ + 1 when a = 0) pays |a|U or |b|U, which is U only at ±1. If a > b ≥ 1, the row is still strictly rising at μ, so a·β_μ − b·β_{μ−1} = (a − b)U + b(β_μ − β_{μ−1}) ≥ U + 1. On the line a = b = t the height is |t|·V. So the minimum is V at t = ±1 alone, and off the line the only vectors at height U are the four named. At J = 1 the conclusion fails, (1, 0) tying (1, 1). The pure products at rank 2 have cofactors 1, x − 1 and 1 + x, of heights U, C(J + 1, ⌊(J + 1)/2⌋) and V, so ph = h and no rank-2 cell fails.
At rank 2 the two minima part by a factor growing as √J
Tier: rule (J = 2…4000).
Verifier: rank2.py::main.
The successive minima λ₁ = V and λ₂ = U, the least height and the second minimum, part as λ₂/λ₁ = U/V = (√e/2)·√(J + 1)·(1 + ε_J), with (J + 1)·ε_J between −0.4166 and 1.2022 at every depth J = 2…4000, and ε_J itself 2.41% at J = 10, −0.41% at J = 99, +0.89% at J = 100 and 0.0075% at J = 2000. Read heuristically, the leading constant is the Gaussian shape of the row: its largest step sits one standard deviation, about √J/2, from the centre, where the row has fallen to e^{−1/2} of its peak. Over the depths read, a rank-2 flattening lattice has one short vector and its second minimum sits the whole gain one difference buys above it.
Open fronts
Which factors can be traded in? Is every traded factor reciprocal with positive coefficients, do finitely many rebuild every failing cell of a given height, and why does a sham of the same sizes rebuild none? Does every rank's band of failing depths end, and how does its last failing depth J_hi(r) grow with the rank? At a band's failing depths a traded pure product attains h on the chart; has h a closed form in the depth there, as it has from J_hi + 1 on over the depths scanned, where the champion attains it? Does the inverse dial's pure law hold at every depth in the columns k ≤ 7? What is the rank-3 analogue of the rank-2 theorem, the growth order of the height-1 column, and the residual of the rank-2 ratio past its leading term?
The chart's ℓ1 twin is the Prouhet–Tarry–Escott problem: a multiple of (x − 1)^J whose ℓ1 norm is 2J is exactly an ideal solution of size J, open at J = 11 and J ≥ 13. Coppersmith, Mossinghoff, Scheinerman and VanderKam (arXiv 2304.11254) sieve the symmetric solutions at J = 11 by their local solutions up to a bound of 3500, the paper's height of a solution, not this page's, and find none, and the least known symmetric solutions at sizes 9 and 10 span 198 and 626, far past the chart's widths. Does an ideal solution of size 11 exist?