diophantus

Log in | Create account
Hello, this is beta version of diophantus. If you want to report about a mistake, please, write to hello@diophantus.org
All articles by
Miller J. | Miller J. M. | Miller Steven J. | Miller M. Coleman | Miller Gerald A. | Miller L. | Miller Jon M. | Miller C. J. | Miller D. J. | Miller G. A.

Steven E. | Steven | Steven M. | Steven Cumming | Steven Darren | Steven Du | Steven Ian R. | Steven S. | Steven Samuel

J | J G. | J S. | J Girish Raguvir | J Ganesh | J Jeya Pradha | J Metilda Sagaya Mary N | J Paul A. Schweitzer S. | J Prabuchandran K. | J Abhijit A

Search results


Walking to Infinity Along Some Number Theory sequences

Miller Steven J., Peng Fei, Popescu Tudor, Siktar Joshua M., Wattanawanichkul Nawapan, Program The Polymath REU
28 Oct 2020 math.NT arxiv.org/abs/2010.14932

An interesting open conjecture asks whether it is possible to walk to infinity along primes, where each term in the sequence has one digit more than the previous. We present different greedy models for prime walks to predict the long-time behavior of the trajectories of orbits, one of which has similar behavior to the actual backtracking one. Furthermore, we study the same conjecture for square-free numbers, which is motivated by the fact that they have a strictly positive density, as opposed to primes. We introduce stochastic models and analyze the walks' expected length and frequency of digits added. Lastly, we prove that it is impossible to walk to infinity in other important number-theoretical sequences or on primes in different bases.

Generalizing Ruth-Aaron Numbers

Jiang Yanan, Miller Steven J.
28 Oct 2020 math.NT arxiv.org/abs/2010.14990

Let $f(n)$ be the sum of the prime divisors of $n$, counted with multiplicity; thus $f(2020)$ $= f(2^2 \cdot 5 \cdot 101) = 110$. Ruth-Aaron numbers, or integers $n$ with $f(n)=f(n+1)$, have been an interest of many number theorists since the famous 1974 baseball game gave them the elegant name after two baseball stars. Many of their properties were first discussed by Erd\"os and Pomerance in 1978. In this paper, we generalize their results in two directions: by raising prime factors to a power and allowing a small difference between $f(n)$ and $f(n+1)$. We prove that the number of integers up to $x$ with $f_r(n)=f_r(n+1)$ is $O\left(\frac{x(\log\log x)^3\log\log\log x}{(\log x)^2}\right)$, where $f_r(n)$ is the Ruth-Aaron function replacing each prime factor with its $r-$th power. We also prove that the density of $n$ remains $0$ if $|f_r(n)-f_r(n+1)|\leq k(x)$, where $k(x)$ is a function of $x$ with relatively low rate of growth. Moreover, we further the discussion of the infinitude of Ruth-Aaron numbers and provide a few possible directions for future study.

An Introduction to Completeness of Positive Linear Recurrence Sequences

Bo?dyriew El?bieta, Haviland John, , Lentfer John, Miller Steven J.,
07 Oct 2020 math.CO arxiv.org/abs/2010.04071

A positive linear recurrence sequence (PLRS) is a sequence defined by a homogeneous linear recurrence relation with positive coefficients and a particular set of initial conditions. A sequence of positive integers is \emph{complete} if every positive integer is a sum of distinct terms of the sequence. One consequence of Zeckendorf's theorem is that the sequence of Fibonacci numbers is complete. Previous work has established a generalized Zeckendorf's theorem for all PLRS's. We consider PLRS's and want to classify them as complete or not. We study how completeness is affected by modifying the recurrence coefficients of a PLRS. Then, we determine in many cases which sequences generated by coefficients of the forms $[1, \ldots, 1, 0, \ldots, 0, N]$ are complete. Further, we conjecture bounds for other maximal last coefficients in complete sequences in other families of PLRS's. Our primary method is applying Brown's criterion, which says that an increasing sequence ${H_n}_{n = 1}^{\infty}$ is complete if and only if $H_1 = 1$ and $H_{n + 1} \leq 1 + \sum_{i = 1}^n H_i$. This paper is an introduction to the topic that is explored further in Completeness of Positive Linear Recurrence Sequences arXiv:2010.01655.

Completeness of Positive Linear Recurrence Sequences

Bo?dyriew El?bieta, Haviland John, , Lentfer John, Miller Steven J.,
04 Oct 2020 math.CO arxiv.org/abs/2010.01655

A sequence of positive integers is complete if every positive integer is a sum of distinct terms. A positive linear recurrence sequence (PLRS) is a sequence defined by a homogeneous linear recurrence relation with nonnegative coefficients of the form $H_{n+1} = c_1 H_n + \cdots + c_L H_{n-L+1}$ and a particular set of initial conditions. We seek to classify various PLRS's by completeness. With results on how completeness is affected by modifying the recurrence coefficients of a PLRS, we completely characterize completeness of several families of PLRS's as well as conjecturing criteria for more general families. Our primary method is applying Brown's criterion, which says that an increasing sequence ${H_n}_{n = 1}^{\infty}$ is complete if and only if $H_1 = 1$ and $H_{n + 1} \leq 1 + \sum_{i = 1}^n H_i$. %A survey of these results can be found in \cite{BHLLMT}. Finally, we adopt previous analytic work on PLRS's to find a more efficient way to check completeness. Specifically, the characteristic polynomial of any PLRS has exactly one positive root; by bounding the size of this root, the majority of sequences may be classified as complete or incomplete. Additionally, we show there exists an indeterminate region where the principal root does not reveal any information on completeness. We have conjectured precise bounds for this region.

Tinkering with Lattices: A New Take on the Erd\H{o}s Distance Problem

Boldyriew Elzbieta, Kim Elena, Miller Steven J., Palsson Eyvindur, Sovine Sean, , Zhao Jason
25 Sep 2020 math.NT arxiv.org/abs/2009.12450

The Erd\H{o}s distance problem concerns the least number of distinct distances that can be determined by $N$ points in the plane. The integer lattice with $N$ points is known as \textit{near-optimal}, as it spans around $O(N/\sqrt{\log(N)})$ distinct distances which is the lower bound for a set of $N$ points (Erd\H{o}s, 1946). The only previous non-asymptotic work relating to the Erd\H{o}s distance problem that has been done was carried out for $N \leq 13$. We take a new non-asymptotic approach to this problem, studying the distance distribution, or in other words, the plot of frequencies of each distance of the $N\times N$ integer lattice. In order to fully characterize this distribution and determine its most common and least common distances, we adapt previous number-theoretic results from Fermat and Erd\H{o}s, in order to relate the frequency of a given distance on the lattice to the sum-of-squares formula. We study the distance distributions of all its possible subsets; although this is a restricted case, we find that the structure of the integer lattice allows for the existence of subsets which can be chosen so that their distance distributions have certain properties, such as emulating the distribution of randomly distributed sets of points for certain small subsets, or that of the larger lattice itself. We define an error which compares the distance distribution of a subset with that of the full lattice. The structure of the integer lattice allows us to take subsets with certain geometric properties in order to maximize error, by exploiting the potential for sub-structure in the integer lattice. We show these geometric constructions explicitly; further, we calculate explicit upper bounds for the error for when the number of points in the subset is $4$, $5$, $9$ or $\left \lceil N^2/2\right\rceil$ and prove a lower bound for more general numbers of points.

Extending Zeckendorf's Theorem to a Non-constant Recurrence and the Zeckendorf Game on this Non-constant Recurrence Relation

Bo?dyriew El?bieta, Cusenza Anna, Dai Linglong, Ding Pei, Dunkelberg Aidan, Haviland John, Huffman Kate, Ke Dianhui, Kleber Daniel, Kuretski Jason
25 Sep 2020 math.NT arxiv.org/abs/2009.12475

Zeckendorf's Theorem states that every positive integer can be uniquely represented as a sum of non-adjacent Fibonacci numbers, indexed from $1, 2, 3, 5,\ldots$. This has been generalized by many authors, in particular to constant coefficient fixed depth linear recurrences with positive (or in some cases non-negative) coefficients. In this work we extend this result to a recurrence with non-constant coefficients, $a_{n+1} = n a_{n} + a_{n-1}$. The decomposition law becomes every $m$ has a unique decomposition as $\sum s_i a_i$ with $s_i \le i$, where if $s_i = i$ then $s_{i-1} = 0$. Similar to Zeckendorf's original proof, we use the greedy algorithm. We show that almost all the gaps between summands, as $n$ approaches infinity, are of length zero, and give a heuristic that the distribution of the number of summands tends to a Gaussian. Furthermore, we build a game based upon this recurrence relation, generalizing a game on the Fibonacci numbers. Given a fixed integer $n$ and an initial decomposition of $n= na_1$, the players alternate by using moves related to the recurrence relation, and whoever moves last wins. We show that the game is finite and ends at the unique decomposition of $n$, and that either player can win in a two-player game. We find the strategy to attain the shortest game possible, and the length of this shortest game. Then we show that in this generalized game when there are more than three players, no player has the winning strategy. Lastly, we demonstrate how one player in the two-player game can force the game to progress to their advantage.

The limiting spectral measure for an ensemble of generalized checkerboard matrices

Chen Fangu, Yu Jiahui, Miller Steven J., Lin Yuxin
22 Sep 2020 math.PR math.SP arxiv.org/abs/2009.10833

Random matrix theory successfully models many systems, from the energy levels of heavy nuclei to zeros of $L$-functions. While most ensembles studied have continuous spectral distribution, Burkhardt et al introduced the ensemble of $k$-checkerboard matrices, a variation of Wigner matrices with entries in generalized checkerboard patterns fixed and constant. In this family, $N-k$ of the eigenvalues are of size $O(\sqrt{N})$ and were called bulk while the rest are tightly contrained around a multiple of $N$ and were called blip. We extend their work by allowing the fixed entries to take different constant values. We can construct ensembles with blip eigenvalues at any multiples of $N$ we want with any multiplicity (thus we can have the blips occur at sequences such as the primes or the Fibonaccis). The presence of multiple blips creates technical challenges to separate them and to look at only one blip at a time. We overcome this by choosing a suitable weight function which allows us to localize at each blip, and then exploiting cancellation to deal with the resulting combinatorics to determine the average moments of the ensemble; we then apply standard methods from probability to prove that almost surely the limiting distributions of the matrices converge to the average behavior as the matrix size tends to infinity. For blips with just one eigenvalue in the limit we have convergence to a Dirac delta spike, while if there are $k$ eigenvalues in a blip we again obtain hollow $k \times k$ GOE behavior.

Bounds on Zeckendorf Games

Cusenza Anna, Dunkelberg Aiden, Huffman Kate, Ke Dianhui, McClatchey Micah, Miller Steven J., Mizgerd Clayton, Tiwari Vashisth, Ye Jingkai, Zheng Xiaoyan
20 Sep 2020 math.NT arxiv.org/abs/2009.09510

Zeckendorf proved that every positive integer $n$ can be written uniquely as the sum of non-adjacent Fibonacci numbers. We use this decomposition to construct a two-player game. Given a fixed integer $n$ and an initial decomposition of $n=n F_1$, the two players alternate by using moves related to the recurrence relation $F_{n+1}=F_n+F_{n-1}$, and whoever moves last wins. The game always terminates in the Zeckendorf decomposition; depending on the choice of moves the length of the game and the winner can vary, though for $n\ge 2$ there is a non-constructive proof that Player 2 has a winning strategy. Initially the lower bound of the length of a game was order $n$ (and known to be sharp) while the upper bound was of size $n \log n$. Recent work decreased the upper bound to of size $n$, but with a larger constant than was conjectured. We improve the upper bound and obtain the sharp bound of $\frac{\sqrt{5}+3}{2}\ n - IZ(n) - \frac{1+\sqrt{5}}{2}Z(n)$, which is of order $n$ as $Z(n)$ is the number of terms in the Zeckendorf decomposition of $n$ and $IZ(n)$ is the sum of indices in the Zeckendorf decomposition of $n$ (which are at most of sizes $\log n$ and $\log^2 n$ respectively). We also introduce a greedy algorithm that realizes the upper bound, and show that the longest game on any $n$ is achieved by applying splitting moves whenever possible.

Generalizing Zeckendorf's Theorem to Homogeneous Linear Recurrences, II

Martinez Thomas C., Miller Steven J., Mizgerd Clay, Murphy Jack, Sun Chenyang
16 Sep 2020 math.NT math.CO arxiv.org/abs/2009.07891

Zeckendorf's theorem states that every positive integer can be written uniquely as the sum of non-consecutive Fibonacci numbers ${F_n}$, where we take $F_1=1$ and $F_2=2;$ in fact, it provides an alternative definition of the Fibonacci numbers. This has been generalized for any Positive Linear Recurrence Sequence (PLRS), which is, informally, a sequence satisfying a homogeneous linear recurrence with a positive leading coefficient and non-negative integer coefficients along with specified initial conditions. Note these legal decompositions are generalizations of base $B$ decompositions. We investigate linear recurrences with leading coefficient zero, followed by non-negative integer coefficients, with differences between indices relatively prime (abbreviated ZLRR), via two different approaches. In our prequel paper, we investigate the first approach which generalizes the definition of a legal decomposition for a PLRS found in Kolo\u{g}lu, Kopp, Miller and Wang. We prove that every positive integer $N$ has a legal decomposition for any ZLRR using the greedy algorithm. We also show that a specific family of ZLRRs do not have uniqueness of decompositions. This paper investigates the second approach, which converts a ZLRR to a PLRR that has the same growth rate. We develop the Zeroing Algorithm, a powerful helper tool for analyzing the behavior of linear recurrence sequences. We use it to prove a very general result that guarantees the possibility of conversion between certain recurrences, and develop a method to quickly determine whether our sequence diverges to $+\infty$ or $-\infty$, given any real initial values.

Winning Strategy for the Multiplayer and Multialliance Zeckendorf Games

Cusenza Anna, Dunkelberg Aidan, Huffman Kate, Ke Dianhui, Kleber Daniel, Miller Steven J., Mizgerd Clayton, Tiwari Vashisth, Ye Jingkai, Zheng Xiaoyan
08 Sep 2020 math.NT arxiv.org/abs/2009.03708

Edouard Zeckendorf proved that every positive integer $n$ can be uniquely written \cite{Ze} as the sum of non-adjacent Fibonacci numbers, known as the Zeckendorf decomposition. Based on Zeckendorf's decomposition, we have the Zeckendorf game for multiple players. We show that when the Zeckendorf game has at least $3$ players, none of the players have a winning strategy for $n\geq 5$. Then we extend the multi-player game to the multi-alliance game, finding some interesting situations in which no alliance has a winning strategy. This includes the two-alliance game, and some cases in which one alliance always has a winning strategy. %We examine what alliances, or combinations of players, can win, and what size they have to be in order to do so. We also find necessary structural constraints on what alliances our method of proof can show to be winning. Furthermore, we find some alliance structures which must have winning strategies. %We also extend the Generalized Zeckendorf game from $2$-players to multiple players. We find that when the game has $3$ players, player $2$ never has a winning strategy for any significantly large $n$. We also find that when the game has at least $4$ players, no player has a winning strategy for any significantly large $n$.