An official website of the United States government
We explore the Collatz conjecture and its variants through the lens of termination of string rewriting. We construct a rewriting system that simulates the iterated application of the Collatz function on strings corresponding to mixed binary–ternary representations of positive integers. Termination of this rewriting system is equivalent to the Collatz conjecture. To show the feasibility of our approach in proving mathematically interesting statements, we implement a minimal termination prover that uses the automated method of matrix/arctic interpretations and we perform experiments where we obtain proofs of nontrivial weakenings of the Collatz conjecture. Finally, we adapt our rewriting system to show that other open problems in mathematics can also be approached as termination problems for relatively small rewriting systems. Although we do not succeed in proving the Collatz conjecture, we believe that the ideas here represent an interesting new approach.
more »
« less
An Automated Approach to the Collatz Conjecture
Abstract We explore the Collatz conjecture and its variants through the lens of termination of string rewriting. We construct a rewriting system that simulates the iterated application of the Collatz function on strings corresponding to mixed binary–ternary representations of positive integers. We prove that the termination of this rewriting system is equivalent to the Collatz conjecture. We also prove that a previously studied rewriting system that simulates the Collatz function using unary representations does not admit termination proofs via natural matrix interpretations, even when used in conjunction with dependency pairs. To show the feasibility of our approach in proving mathematically interesting statements, we implement a minimal termination prover that uses natural/arctic matrix interpretations and we find automated proofs of nontrivial weakenings of the Collatz conjecture. Although we do not succeed in proving the Collatz conjecture, we believe that the ideas here represent an interesting new approach.
more »
« less
- Award ID(s):
- 2006363
- PAR ID:
- 10408919
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Journal of Automated Reasoning
- Volume:
- 67
- Issue:
- 2
- ISSN:
- 0168-7433
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P 6⊆ NC1). Karchmer, Raz, and Wigderson [KRW95] suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions f ⋄ g. They showed that the validity of this conjecture would imply that P 6⊆ NC^1 . Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function f, but only for few inner functions g. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function g whose depth complexity can be lower bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the s-t-connectivity, clique, and generation functions. In order to carry this progress back to the non-monotone setting, we introduce a new notion of semi-monotone composition, which combines the non-monotone complexity of the outer function f with the monotone complexity of the inner function g. In this setting, we prove the KRW conjecture for a similar selection of inner functions g, but only for a specific choice of the outer function f.more » « less
-
We study the variation of $$\unicode[STIX]{x1D707}$$ -invariants in Hida families with residually reducible Galois representations. We prove a lower bound for these invariants which is often expressible in terms of the $$p$$ -adic zeta function. This lower bound forces these $$\unicode[STIX]{x1D707}$$ -invariants to be unbounded along the family, and we conjecture that this lower bound is an equality. When $$U_{p}-1$$ generates the cuspidal Eisenstein ideal, we establish this conjecture and further prove that the $$p$$ -adic $$L$$ -function is simply a power of $$p$$ up to a unit (i.e. $$\unicode[STIX]{x1D706}=0$$ ). On the algebraic side, we prove analogous statements for the associated Selmer groups which, in particular, establishes the main conjecture for such forms.more » « less
-
Ta-Shma, Amnon (Ed.)We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over 𝔽₂. Our main contributions include: 1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible. 2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results." 3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction. 4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric.more » « less
-
We prove the Turaev-Viro invariants volume conjecture for a "universal" class of cusped hyperbolic 3-manifolds that produces all 3-manifolds with empty or toroidal boundary by Dehn filling. This leads to two-sided bounds on the volume of any hyperbolic 3-manifold with empty or toroidal boundary in terms of the growth rate of the Turaev-Viro invariants of the complement of an appropriate link contained in the manifold. We also provide evidence for a conjecture of Andersen, Masbaum and Ueno (AMU conjecture) about certain quantum representations of surface mapping class groups. A key step in our proofs is finding a sharp upper bound on the growth rate of the quantum 6j−symbol evaluated at q=e2πir.more » « less
