Matching works

14 works

math.NT — Number Theory

Realizer Bounds and Repetition Constraints at the First Coefficient Crossing in the 3x + 1 Problem

Contributed by Elias De Jesús

Terras’s coefficient stopping time conjecture asks whether the shortcut Collatz orbit of every integer n ≥ 2 lies below n when its coefficient ρk = 3d/2k first falls below one. Here k counts shortcut steps and d counts their odd inputs. We prove that every eligible realizer descends when the first-crossing word has at most 75 maximal runs of odd inputs. Any counterexample requires at least 76 such runs, 10 439 860 591 steps and 6 586 818 670 odd inputs. The proof uses a lower bound on the seed from the length of its odd runs, rational approximations to log2 3, the verified range of Rozier and Terracol, and Rhin’s estimate for a linear form in logarithms. We also prove descent for a family with arbitrarily many odd runs. Two further restrictions narrow the remaining words. An initial square U U in a failing word satisfies |U | < 35 log2 k. For a counterexample of shortest crossing length, the reciprocal-sum estimate of Nikzad, Frinkle and Bagherzadeh gives a lower bound on ρk whose value begins 0.9441733669 . . .. The open inequality compares the least eligible starting value in each remaining parity class with an explicit threshold.

A mix of human-written and AI-generated textHuman understanding: some parts2-adic congruencesCollatz conjectureDiophantine approximationTerras conjecturecoefficient stopping timefirst coefficient crossingleast positive realizersodd-run decompositionparity vectorsreciprocal sums
Nov 15, 202612 pages
PDFView work

math.CA — Classical Analysis and ODEs

Certified lower bounds for the first and the signed third autocorrelation constants

Contributed by Tejasvi Singh Tomar

Let C1C_1 be the largest constant such that sup⁡∣t∣≤1/2∫f(t−x)f(x) dx≥C1(∫−1/41/4f)2\sup_{|t|\le 1/2}\int f(t-x)f(x)\,dx\ge C_1\bigl(\int_{-1/4}^{1/4}f\bigr)^2 for every nonnegative function ff on the real line. We prove C1≥1.337C_1\ge 1.337, improving the bound 1.29371.2937 of Kim and Pilanci, by a spatial branch-and-bound over the masses of ff on equal bins. Consequently, for every large gg, every gg-Sidon set in {1,…,N}\{1,\dots,N\} has fewer than 1.2231gN1.2231\sqrt{gN} elements once NN is large enough in terms of gg. For real-valued ff supported in [−1/4,1/4][-1/4,1/4], let C3C_3 and C3′C_3' be the analogous constants for the essential suprema of ∣f∗f∣|f*f| and of f∗ff*f; no lower bound better than the trivial bound 11 was recorded for them. We prove C3≥C3′≥4/3C_3\ge C_3'\ge 4/3 with the argument principle. Both proofs are computer-assisted, and both theorems are also proved in Lean 4.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715655

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

math.NT — Number Theory

Consecutive Divisors of Sums of Fibonacci Polynomials: a Luca–Marques Analogue in Finite-Field Polynomial Rings

Contributed by Scott Kominers

For every prime power qq with gcd⁡(q,6)=1\gcd(q,6)=1, we construct infinitely many pairs of consecutive monic polynomials in Fq[T]\mathbb{F}_q[T] whose product divides the Fibonacci-polynomial sum with upper index one less than their common norm. This gives a function-field counterpart of the divisibility condition in the Luca–Marques theorem on consecutive integral arithmetic means of Fibonacci numbers. A short extension of the construction gives infinitely many triples of consecutive monic polynomials with the same property.

Author comments: Dedicated to the memory of Florian Luca

A mix of human-written and AI-generated textHuman understanding: all partsFibonacci polynomialsLucas polynomialsfunction fieldspolynomial recurrences
Nov 10, 20268 pages
PDFView work

math.NT — Number Theory

A congruence modulo p^2 for the p-th coefficient of e(1-z)^((1-z)/z)

Contributed by David Niedbala Giraudin

Define E_n by sum_{n>=0} E_n z^n = exp(sum_{k>=1} z^k/(k(k+1))) = e(1-z)^((1-z)/z). Equivalently, e(1+1/x)^(-x) = sum_{n>=0} E_n (x+1)^(-n), the reciprocal of the expansion of e^(-1)(1+1/x)^x used by Yang in refinements of Carleman's inequality. We prove that for every odd prime p, E_p = -p/2 (mod p^2); in particular v_p(E_p) = 1. The proof is elementary. With Phi(u) = e(1+u)^(-1/u), it combines the two expressions of E_p through the coefficients of Phi that come from the identities e(1-z)^((1-z)/z) = Phi(-z)/(1-z) and e(1-z)^((1-z)/z) = Phi(z/(1-z)), and it reduces the congruence to the differential recurrence of the E_n read modulo p. A script checks the statement and the intermediate congruences for all odd primes below 200 and a few larger ones.

Primarily AI-generated textHuman understanding: no partsCarleman's inequalitycongruences modulo p^2harmonic numbersp-adic valuationpower series coefficients
Nov 04, 20264 pages
PDFView work

math.NT — Number Theory

The p-adic valuations of the coefficients in Yang's expansion of (1+1/x)^x

Contributed by David Niedbala Giraudin

Yang's coefficients b_n, defined by (1+1/x)^x = e(1 - sum_{n>=1} b_n (x+1)^{-n}), appear in refinements of Carleman's inequality, and the literature on them concerns their analytic properties. We study their p-adic valuations for an odd prime p. From the identity 1 - sum_n b_n u^n = exp(-sum_{k>=1} u^k/(k(k+1))) one gets v_p(b_n) >= -M(n), where M(n) is the optimum of a knapsack problem on the compositions of n. We compute M(n) in closed form and show that, for n >= 2, the optimum is attained by a unique composition exactly when n = (p-1)m with m in an explicit set U_p defined by a digit condition. For these n the bound is an equality: v_p(b_n) = -(m + v_p(m!)). The set U_p has density 1/(p-1), so the valuation of b_n is determined on a set N_p of indices of density 1/(p-1)^2. The set N_p contains the indices p^K - 1, at which b_{p^K-1} is the unique coefficient of minimal valuation among b_1, ..., b_{p^K-1}. The same statements hold for the coefficients of e(1-u)^{1/u}, and the minimality statement for those of e(1-u)^{1/u-1}. A script checks all statements numerically in finite ranges.

Primarily AI-generated textHuman understanding: no partsCarleman's inequalityKummer's theoremcompositionsknapsack problemp-adic valuationsums of digits
Nov 04, 20265 pages
PDFView work

math.NT — Number Theory

On Bounds for Reciprocal Sums and Residues in Collatz Orbits, and Their Consequences

Contributed by Behzad Nikzad, Karl Frinkle, Fatemeh Bagherzadeh

We prove uniform bounds for reciprocal sums and residue products along Collatz paths. Let F\mathcal F be a finite nonrepeating shortcut path whose input states are greater than 11, let RF\mathcal R_{\mathcal F} be the sum of the reciprocals of its odd inputs, and let ρF\rho_{\mathcal F} be its finite-path residue. Then RF<1,ρF<43.\mathcal R_{\mathcal F}<1, \qquad \rho_{\mathcal F}<\frac{4}{3}. For the first-arrival trajectory of a terminating positive integer nn, these inequalities give R(n)<1,ρ(n)=2E(n)3O(n)n<43,\mathcal R(n)<1, \qquad \rho(n)=\frac{2^{E(n)}}{3^{O(n)}n}<\frac{4}{3}, where E(n)E(n) and O(n)O(n) are the division and odd-operation counts. More generally, when each odd value greater than 11 is counted once, the corresponding reciprocal-sum and residue bounds hold for every forward orbit, without a termination assumption. The proof combines verified finite height-delay records and residue bounds, canonical-block reciprocal estimates, and an exact finite count organized by gap brackets. Gap brackets, closely related to parity vectors, record the divisions by two between successive odd inputs and organize the finite counting argument; together with a related coordinate representation, they also yield exact formulas for reconstructing finite trajectories. After taking base-22 logarithms, the bound ρF<4/3\rho_{\mathcal F}<4/3 leaves an uncertainty of less than 1/21/2 in the relation between the even- and odd-operation counts. Since these counts are integers, either count is determined exactly by the other count and the path endpoints. We obtain nearest-integer restrictions on the changes in EE and OO between adjacent integers, apart from explicit small exceptions, and prove that adjacent terminating integers of equal height have identical operation counts. Thus every equal-height streak lies in a single operation-count class. We further introduce the charge λ=E−2O\lambda=E-2O and associated height and charge slice functions to study the persistence and eventual break of equal-height streaks. We distinguish class records, which are the least starting integers attaining specified values, from delay records, which attain new extrema relative to all smaller starting integers. The resulting record theory shows that λ\lambda-delay records form a subsequence of the odd-count delay records, which form a subsequence of the common division-count and height-delay list. On the class side, the nonpositive charge-class records lie among the odd-count class records, which lie among the division-count class records, which in turn lie among the height-class records. The corresponding hierarchies also hold for first-arrival paths to a common endpoint zz when z=1z=1 or when z>2z>2 is nonperiodic under the shortcut map.

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 03, 2026127 pages
PDFView work

math.NT — Number Theory

The binary Collatz dynamics of the trinomials x^n+x+1: an independent proof of two conjectures of Gallardo and Rahavandrainy

Contributed by David Niedbala Giraudin

Gallardo and Rahavandrainy studied an analogue of the Collatz map on F_2[x], in which x(x+1) plays the role of 2 and x^2+x+1 that of 3: an odd polynomial A is sent to the odd part of 1+(x^2+x+1)A. They proved that every orbit reaches 1, and conjectured that the orbit of the trinomial x^n+x+1 has length 2^s+1, where s is the largest integer with 2^(s+1) < n, and that for 1 <= t <= s-1 it contains 2^t terms of the same degree. We prove both statements for every n >= 3. They were proved earlier, with a complete Lean 4 formalization, by W. Choi; the proof given here was obtained independently. The proof rests on the identity (x^2+x+1)+x(x+1)=1: it reduces the dynamics to a map from one plateau to the next, characterises the last plateau of any orbit, and shows that along the orbit of x^n+x+1 the plateaus start at the 2^j-th powers of the odd parts of the polynomials x^m(x^2+x+1)+1, the index m following an explicit binary recursion. We also note that a later restatement of the conjecture, with a non-strict inequality, fails exactly when n is a power of 2. A script checks all the statements numerically.

Primarily AI-generated textHuman understanding: no parts
Nov 03, 20266 pages
PDFView work

math.NT — Number Theory

Powers of a Prime in the Image of Summatory Valuation Functions

Contributed by Frank Vega

J.-L. Nicolas asked how often a power of 22 belongs to the image of c(n)=∑k≤n2v2(k)c(n)=\sum_{k\le n}2^{v_2(k)}, where v2v_2 is the 22-adic valuation, and showed that the number A(x)A(x) of exponents a≤xa\le x with 2a2^a in the image and the number B(x)B(x) of the other exponents both tend to infinity. We prove that 2a2^a lies in the image of cc if and only if 2a+32^{a+3} is a sum of distinct terms of the superincreasing sequence (j2j)j≥1(j2^j)_{j\ge1}. For every exponent there is at most one possible largest term KK, given by K+⌈log⁡2K⌉=a+3K+\lceil\log_2K\rceil=a+3, and membership is then decided by an explicit recursion on pairs of integers at most a+3a+3, in at most a+1a+1 steps. The exponents without such a KK and the exponents decided in at most one step form explicit infinite families, described completely, which contain the three families of Nicolas. The states of the recursion form a forest and the set of successful states is symmetric; this yields further explicit families and the bounds A(x)≥(3.9655…+o(1))log⁡2xA(x)\ge(3.9655\ldots+o(1))\log_2x and B(x)≥(2.8178…+o(1))log⁡2xB(x)\ge(2.8178\ldots+o(1))\log_2x, whereas the families of Nicolas give the constants 12\frac12 and 32\frac32. The reduction, the unique candidate, the recursion and the symmetry extend to cp(n)=∑k≤npvp(k)c_p(n)=\sum_{k\le n}p^{v_p(k)} for every prime pp. Computations in exact integer arithmetic reproduce the table of Nicolas and give A(x)A(x) for x≤262000x\le262000, with A(x)/xA(x)/x between 0.51320.5132 and 0.87500.8750 for x=1000,2000,…,262000x=1000,2000,\dots,262000.

Author comments: In this new version, we add new computer-based experiments.

Primarily AI-generated textHuman understanding: all parts$2$-adic valuationArithmetic functionsBinary expansionOpen questions of NicolasPolynomials over $\mathbb{F}_2$Superincreasing sequences
Nov 03, 202629 pages
PDFView work

math.NT — Number Theory

Positive density of Collatz convergence at every rate above 3/log(4/3)

Contributed by Idris Ali Shaik

We prove that a positive proportion of positive integers reach 1 within c log x ordinary Collatz steps for every fixed c > 3/log(4/3), with one positive lower natural-density bound independent of c. For each fixed positive target not divisible by three, the same range of times holds with a target-dependent bound, irrespective of its subsequent orbit. Targets divisible by three have predecessor basins of natural density zero. Diagonalization gives one positive-density set with a vanishing excess above the limiting time coefficient. The proof extends weighted inverse trajectories from a fixed finite family of roots and preserves positive weighted mass at every sufficiently large scale. We derive an explicit Fourier-decay estimate, at frequencies not divisible by three, for an auxiliary distribution on residue classes. Its proof uses paired geometric valuations and their exact binomial first-passage law. At order 6409, the coefficient C satisfies log_2 log_2 log_2 C < 176, compared with > 2^172 for the explicit coefficient in Mazur's work. Fractional-moment certificates, residue-capacity bounds, and an enlarged family of roots give explicit density estimates after harmonic and dyadic counting. Further refinements locate surviving mass within the root family, retain conditional residue information, and recover additional distinct sources with a bounded extra step cost. The primitive-decay theorem and the main qualitative density conclusions are formalized in Lean 4. The coefficient-size comparison and the complete optimized density bounds remain paper proofs.

A mix of human-written and AI-generated textHuman understanding: all partsCollatz problemFourier decayformal verificationhitting timesinverse trajectorieslower natural density
Oct 26, 2026100 pages
PDFView work

math.NT — Number Theory

Polylogarithmic Descent for Almost All Collatz Orbits in Natural Density

Contributed by Idris Ali Shaik

Korec proved that, for each fixed θ > log 3/log 4, almost every positive integer n has a Collatz iterate below n^θ in natural density. Tao proved descent below every prescribed diverging threshold in logarithmic density. We obtain polylogarithmic descent in ordinary natural density within logarithmically many steps, with bounds on the preceding orbit values. The shortcut map T sends even n to n/2 and odd n to (3n+1)/2. The unaccelerated map Col sends even n to n/2 and odd n to 3n+1. For any prescribed positive function f(n) → ∞, however slowly, we prove that almost every positive integer n, in natural density, has nonnegative integers k = k(n) and ℓ = ℓ(n) satisfying T^k(n) = Col^ℓ(n) < (log n)^A_FP f(n), where A_FP ≈ 9.9911 is an explicit exponent. The shortcut time is k = c_* log n + O_f(√(log n log log n)), where c_* = 2/log(4/3). The leading time c_* log n is predicted by the average logarithmic contraction of the equally weighted multipliers 1/2 and 3/2. The unaccelerated time is ℓ = (3/2)c_* log n + O_f(√(log n log log n)). Both orbits are bounded by nf(n) up to their respective times. For each fixed A > A_FP, put q = A/(2A_FP) − 1/2. For sufficiently large X, all but at most C_A X/(log X)^q integers n ≤ X satisfy the same conclusions with target (log n)^A and bound n(log n)^q on both orbits. The constant C_A and the time-error constants depend only on A. The proof counts finite parity sequences exactly and follows first passages through decreasing thresholds. We count later failures among the original starting values, without assuming that values reached after a descent are uniformly distributed. For starting values 2^M ≤ n < 2^(M+1), only O(√(M log M)) cumulative passage times need to be counted at each threshold. A finite random-walk survival estimate supplies the additional saving needed at the critical exponent. Density-one descent below a fixed multiple of (log n)^A_FP is not established, and the pointwise Collatz conjecture remains open. The theorem for arbitrary f is formalized in Lean 4 with Mathlib and registered as PALOMAR-2026-08-26-000005, version 4.

A mix of human-written and AI-generated textHuman understanding: all partsCollatz mapalmost all Collatz orbitsfirst passagenatural densityparity vectorspolylogarithmic descentstopping time
Oct 17, 202624 pages
PDFView work

math.NT — Number Theory

Finite Valuation Words and Terminal Obstructions for the Accelerated Syracuse Map

Contributed by Tosho Karadzhov

We develop a finite-word obstruction framework for the accelerated Syracuse map on positive odd integers. A finite valuation word determines an exact iterate formula and a unique realization class modulo a power of two; compatible infinite prefixes define a natural two-adic inverse-limit object together with least positive representatives. The first part records the exact finite-word congruence machinery, finite-descent equivalence, terminal-surplus identity, terminal-ceiling break criterion, bad-prefix windows, activated density collapse, stabilization criterion, and strict-jump bookkeeping. The second part uses these tools to isolate terminal obstruction classes for a hypothetical counterexample: a bounded branch leading to a nontrivial accelerated cycle, and an unbounded eventual no-jump branch, successively reduced through a chain of geometric and combinatorial normal forms to a packet-surplus compensation target. The resulting reduction spine is lossless: Collatz follows from exclusion of nontrivial accelerated cycles together with a packet-surplus, or stronger record-ladder, compensation theorem for the unbounded branch. As a closed module, we include a closed class-exclusion theorem showing that no eventually periodic infinite low-surplus valuation chain is realized by a positive odd integer. On the bounded branch, we further record, as an explicit unproved roadmap step, that the terminal-ceiling strict-jump obstruction reduces to a single recurrent valuation-mismatch statement. This manuscript proves the architecture stated in its theorems, propositions, lemmas, and corollaries; it states the remaining terminal exclusions explicitly as problems, conjectures, or roadmap steps, and does not claim a completed proof of the full Collatz conjecture.

Primarily AI-generated textHuman understanding: no parts3x+1 problemCollatz conjectureaccelerated Syracuse maplow-surplus chainsterminal obstructionsvaluation words
Oct 16, 202686 pages
PDFView work

math.NT — Number Theory

Explicit positive lower density for the Collatz Conjecture

Contributed by Kenny Lau

Lech Mazur proved that a positive proportion of integers nn reach 11 under the Collatz map in at most 10.46log⁡n10.46\log n steps. We give a quantitative refinement of his construction. For every NN, at least ⌊N/222163⌋\lfloor N/2^{2^{2^{163}}} \rfloor odd positive integers n<Nn<N reach 11 within 10.46log⁡n10.46\log n ordinary steps and 3.4881log⁡n3.4881\log n accelerated steps. We also obtain results for paths that include any prescribed integer tt not divisible by 33. AxiomProver was used to obtain and formalize this result in Lean.

A mix of human-written and AI-generated textHuman understanding: some partsCollatz conjecturearithmetic dynamics
Oct 14, 202671 pages
PDFView work

math.CO — Combinatorics

Tilings of an equilateral triangle by at most five lattice trapezoids with 60° base angles: a complete structural classification

Contributed by Gonzalo Barria

We study tilings of an equilateral triangle of side n in the triangular grid by k lattice trapezoids with base angles 60°, the objects behind the OEIS sequences A389392 (k = 4) and A391498 (k = 5). We prove two angle identities valid for every such tiling and a lemma relating the number of boundary vertices to the number of pieces having a side on the boundary. With these tools we show that there are exactly 1, 2 and 13 combinatorial types of tilings for k = 3, 4, 5. For k = 3 every tiling is a pinwheel. For k = 4 every tiling belongs to one of the two categories used in A389392, a fact that had previously been taken for granted. For k = 5 the thirteen types refine the eight categories of A391498; in three of them a piece has no side on the boundary. As a consistency check, the volumes of the parameter polytopes together with the generic multiplicities reproduce the leading coefficient 7/36 of the conjectured quasi-polynomial for A391498. All lemmas were checked against an exhaustive enumeration of the tilings with pairwise distinct pieces for n ≤ 15. Finally, the classification turns the thirteen types into eight explicit families of sets of shapes, and an inclusion–exclusion over them reduces the conjectured generating function of A391498 to twelve elementary counting statements, and we settle all twelve: the resulting closed formula reproduces the sequence for every n ≤ 127.

A mix of human-written and AI-generated textHuman understanding: all partsOEIS A391498lattice trapezoidsquasi-polynomialrational generating functiontilings of an equilateral triangle
Oct 01, 202623 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations