title: "Computational material for Fuchs extremal problem"
instructions: |-
  # Exact computations for the Fuchs extremal problem
  
  The programs in this directory use the Python standard library only. They
  were run with Python 3.12.14. Python 3.10 or newer is sufficient. No numerical
  linear algebra package, arbitrary-precision floating-point package, or
  external solver is required.
  
  Run the commands below from this `supplement` directory. All coefficient
  lists are in ascending order, so `[1, 2, 1]` denotes `1 + 2*z + z**2`.
  
  ## Normalization
  
  Write
  
  ```
  J_lambda(P) = integral |1-exp(i*theta)|^(2*lambda) |P(exp(i*theta))|^2 dtheta / (2*pi)
  c0(lambda) = Gamma(2*lambda+1) / Gamma(lambda+1)^2
  ```
  
  The exact lattice objective stored as `normalized_best` or
  `normalized_minimum` is `J_lambda(P)/c0(lambda)`. For a rational parameter,
  the normalized Fourier coefficients are rational:
  
  ```
  r_0 = 1
  r_(j+1) = -r_j * (lambda-j)/(lambda+j+1)
  ```
  
  Every equality comparison, branch bound, and candidate ordering in the
  lattice and product searches uses exact integer or rational arithmetic.
  The field `integral_over_2pi_display` is a
  floating-point decimal presentation of `J_lambda(P)`; it is never used in
  a search decision.
  
  ## Reproducing the computations
  
  First run the small independent checks:
  
  ```bash
  python validate_enumeration.py --output results/enumeration_validation.json
  ```
  
  This makes 97 checks: a separate Cartesian-product search for small
  degrees; the proved formulas on the first two parameter intervals; all
  minimizers at lambda=1 in the checked degrees; and the handling of a
  deliberately interrupted search.
  
  The arithmetic constructions and the critical parameter have separate
  verification programs:
  
  ```bash
  python verify_pte.py
  python verify_pell.py
  python critical_point.py --output results/critical_point.json
  ```
  
  `verify_pte.py` reads `pte_pairs.json`. It checks the displayed PTE pairs,
  disjointness and cardinalities, all required moments, the exact vanishing
  order, monicity and degrees of the quotient polynomials, and the
  nonpalindromic example. It also checks the size-twelve witness for the
  upper bound at parameter eleven, the explicitly displayed pure products,
  and the rational inequalities used in the uniform product-exclusion
  intervals. The pure-product lower bounds from Maltby and Cipu are cited
  mathematical inputs; the program verifies their displayed attaining
  products and the interval estimates derived from those inputs.
  
  `verify_pell.py` checks the first six nontrivial Pell pairs, including
  their parity, disjoint supports, vanishing moments through order three,
  the exact fourth-moment formula, and the increasing separations of the
  displayed clusters. It also checks the first two monic quotients and the
  rational limiting energy factor at `alpha=1/4`. These checks use integer
  and rational arithmetic. The infinite-family construction and its limit
  are proved analytically in the paper.
  
  `critical_point.py` approximates the unique minimum on the third interval.
  It uses 90-digit `Decimal` arithmetic, recurrence to arguments at least
  100, and 20 Bernoulli terms for the digamma and log-gamma expansions. The
  JSON output records analytic truncation bounds and numerical endpoint
  evaluations. This is not directed-rounding interval arithmetic, and
  ordinary arithmetic rounding is not propagated as an interval enclosure;
  the printed digits and bracket are numerical approximations. Existence
  and uniqueness of the critical parameter follow from the paper's
  analytic monotonicity proof. This program locates that unique critical
  point and evaluates the corresponding extremal value.
  
  Reproduce the complete product-family searches on the noninteger
  quarter-grid with the following commands:
  
  ```bash
  python exact_products.py --degree 34 --parameters 1/4,1/2,3/4,5/4,3/2,7/4,9/4,5/2,11/4,13/4,7/2,15/4,17/4,9/2,19/4,21/4,11/2,23/4 --output results/products_n34.json --csv results/products_n34.csv
  python exact_products.py --degree 80 --parameters 1/4,1/2,3/4,5/4,3/2,7/4,9/4,5/2,11/4,13/4,7/2,15/4,17/4,9/2,19/4,21/4,11/2,23/4 --output results/products_n80.json --csv results/products_n80.csv
  ```
  
  Reproduce the full-lattice searches:
  
  ```bash
  python run_computations.py
  ```
  
  The default run includes every noninteger quarter-grid parameter above 3
  at degree 34, two additional analytic cross-checks at that degree, the
  degree-61 nonproduct witness, and the six degree-80 parameters reported
  in the paper. The common node limit is 10,000,000; the lambda=17/4,
  degree-80 case has a separate limit of 100,000,000. These limits reproduce
  the completion statuses in the supplied data. The longest completed case
  in the reference run visited 34,239,539 nodes and took about 289 seconds.
  Elapsed times depend on the machine and on concurrent work.
  
  A selected portion can be rerun, for example:
  
  ```bash
  python run_computations.py --degrees 34 --parameters 13/4,7/2,15/4
  python run_computations.py --degrees 61 --parameters 17/4
  python run_computations.py --degrees 80 --parameters 17/4
  ```
  
  Then build and verify the combined tables and the nonproduct comparison:
  
  ```bash
  python run_computations.py --summarize-only
  python degree34_quarter_grid.py
  python verify_nonproduct_witness.py
  python verify_results.py
  ```
  
  `degree34_quarter_grid.py` produces all 24 rows for
  `lambda = 1/4, 1/2, ..., 6`. Rows up to 3 use the finite-degree analytic
  theorems, integer rows use explicit PTE witnesses and the integer lower
  bound, and the nine remaining noninteger rows require completed exact
  lattice searches. The program checks each reported polynomial value
  again in rational arithmetic.
  
  ## Exact lattice algorithm
  
  For degree `n`, write `P(z) = z**n + sum(a_j*z**j, j<n)`. The normalized
  objective is
  
  ```
  a^T C a + 2*d^T a + 1,
  C_ij = r_|i-j|,   d_i = r_(n-i).
  ```
  
  The matrix `C` is positive definite. The code computes its exact rational
  `L D L^T` decomposition, the center `xi = -C^(-1)d`, and the minimum of
  the real relaxation. Coordinates are enumerated from `a_(n-1)` down to
  `a_0`.
  
  For each coordinate, all coefficients in the conditional center have a
  fixed denominator `q_i`. After clearing a single common denominator,
  its contribution to the remaining norm is
  
  ```
  w_i * (q_i*a_i - p_i)^2,
  ```
  
  where `w_i` is a positive integer and `p_i` is an integer determined by
  the already assigned coordinates. If the remaining integer budget is
  `R`, the exact allowed coordinate range is obtained from
  
  ```
  h = isqrt(R // w_i)
  ceil((p_i-h)/q_i) <= a_i <= floor((p_i+h)/q_i).
  ```
  
  Consequently no rounded square root, floating-point factorization, or
  numerical tolerance can discard a point. At each leaf the original
  Toeplitz objective is recomputed independently in rational arithmetic
  and checked against the triangular expression. A better incumbent
  shrinks the remaining bound exactly. Positive definiteness makes the
  initial ellipsoid finite.
  
  The number `nodes` counts recursive states visited, including the root
  and leaves. It does not count the cost of the rational factorization or
  the number of integer products in the restricted family. `leaves` counts
  complete integer coefficient vectors reached. The node limit is checked
  before entering a new state.
  
  ## Degree bounds and canonical representatives
  
  A full search over monic polynomials of exact degree `n` also gives the
  minimum over all degrees at most `n`: multiply a lower-degree polynomial
  by the necessary power of `z`. This changes neither its monicity nor its
  unit-circle integral.
  
  Canonicalization removes only initial zero entries of the ascending
  coefficient list, corresponding to division by a monomial. It does not
  identify a polynomial with its reversal, change its sign, impose
  palindromicity, or impose nonnegative coefficients. All lattice searches
  allow unrestricted integer coefficients. `canonical_ties` lists the
  different monomial classes found at the best value. For a completed
  search it lists all such minimizing classes.
  
  ## Result statuses
  
  * `complete`: every integer point relevant to the final bound was
    exhausted. `normalized_minimum` is an exact finite-degree minimum.
  * `node_limit`: enumeration stopped at the stated budget.
    `normalized_minimum` is null; `normalized_best` is the value of an
    explicit polynomial and supplies an upper bound only.
  * `incumbent_only`: an atomic checkpoint of an explicit candidate. It
    carries no assertion that enumeration has completed.
  * `complete_product_family`: all sorted positive length tuples with
    `sum(L_i-1) <= N` were visited for `k=floor(lambda)` factors. This
    asserts optimality in that specified product family only.
  
  The latter family is enumerated by `exact_products.py`. It expands
  `Q(z)=product(1-z**L_i)`, evaluates with the fractional parameter
  `alpha=lambda-k`, and clears a common denominator so that all family
  comparisons are integer comparisons. The stored best value is also
  checked using the original polynomial and the parameter `lambda`.
  
  ## Principal results stored in the package
  
  All nine noninteger quarter-grid rows above 3 at degree 34 are complete.
  The six degree-80 rows have the following statuses:
  
  | lambda | Status | J_lambda of best polynomial | Nodes |
  |---|---|---:|---:|
  | 3/2 | complete | 2.54657612407344 | 1,398 |
  | 5/2 | complete | 4.24558822274823 | 149,987 |
  | 7/2 | complete | 5.94879610576467 | 2,226,136 |
  | 17/4 | complete | 7.76259340993152 | 34,239,539 |
  | 9/2 | node_limit | 8.22959550385720 | 10,000,000 |
  | 11/2 | node_limit | 9.90817807064279 | 10,000,000 |
  
  At lambda=17/4 the unique minimizing monomial class at both degrees 61
  and 80 is represented by
  
  ```
  P(z) = (1-z**9-z**10+z**31+z**34-z**55-z**56+z**65)/(1-z)**4.
  ```
  
  The degree-61 search completed after 3,894,122 nodes. Its value is
  strictly below the exact degree-80 four-factor product-family minimum
  7.80944775164424. `results/nonproduct_17_4.json` records the sparse
  numerator, the full coefficient list, the relevant moment identities,
  and the positive exact rational difference. The argument is therefore
  independent of a decimal comparison.
  
  ## Files and integrity checks
  
  This archive omits four duplicate CSV views. The exact JSON records are
  retained, and the commands above regenerate the CSV files when needed.
  
  * `results/toeplitz_lambda_..._n....json`: individual full-lattice runs,
    with exact values, all minimizing monomial classes when complete,
    visited nodes, timing, and the hash of `exact_toeplitz.py`.
  * `results/toeplitz_summary.json`: a combined view of those
    runs, preserving the complete/incomplete distinction.
  * `results/degree34_quarter_grid.json`: the full exact
    quarter-grid table with its analytic or enumerative source stated in
    every row.
  * `results/products_n34.json` and `results/products_n80.json`: the exact
    restricted-family searches.
  * `results/nonproduct_17_4.json`: the strict nonproduct comparison.
  * `results/enumeration_validation.json`: the 97 small and analytic checks.
  * `pte_pairs.json`: the fixed arithmetic witnesses and rational constants
    used by `verify_pte.py`.
  * `results/critical_point.json`: high-precision numerical values for the
    critical parameter, with the analytic truncation bounds and arithmetic
    status explicitly recorded.
  
  `verify_results.py` checks the recorded script hashes, recomputes the
  stored lattice and product polynomial values exactly, checks the status fields, and checks
  the summaries against the individual records. It is a fast integrity
  check. Reexecuting `run_computations.py` reproduces the exhaustive
  enumerations themselves. File hashes change if a script is edited;
  regenerate the affected experiment files after any such change.