On Zaremba's Conjecture

Let $(u_n)_{n \geq 0}$ be a nondegenerate linear recurrence of integers, and let $\mathcal{A}$ be the set of positive integers $n$ such that $u_n$ and $n$ are relatively prime. We prove that $\mathcal{A}$ has an asymptotic density, and that this density is positive unless $(u_n / n)_{n \geq 1}$ is a linear recurrence.

In this paper we generalize some of our results from, `A note on Farey fractions with odd denominators' to subsets of Farey fractions consisting of fractions with denominators not divisible by a given prime. We also investigate the joint distribution of numerators of differences of h-tuples of consecutive fractions in these sets.

In this paper we obtain a sharp upper bound for the number of solutions to a certain diophantine inequality involving fractions with power denominator. This problem is motivated by a conjecture of Zhao concerning the spacing of such fractions in short intervals and the large sieve for power modulus. As applications of our estimate we show Zhao's conjecture is true except for a set of small measure and give a new $\ell_1 \rightarrow \ell_2$ large sieve inequality for power mod...

We show that for any positive forward density subset N \subset Z, there exists an integer m>0, such that, for all n>m, N contains almost perfect n-scaled reproductions of any previously chosen finite set of integers.

We consider sets of positive integers containing no sum of two elements in the set and also no product of two elements. We show that the upper density of such a set is strictly smaller than 1/2 and that this is best possible. Further, we also find the maximal order for the density of such sets that are also periodic modulo some positive integer.

When $A$ and $B$ are subsets of the integers in $[1,X]$ and $[1,Y]$ respectively, with $|A| \geq \alpha X$ and $|B| \geq \beta X$, we show that the number of rational numbers expressible as $a/b$ with $(a,b)$ in $A \times B$ is $\gg (\alpha \beta)^{1+\epsilon}XY$ for any $\epsilon > 0$, where the implied constant depends on $\epsilon$ alone. We then construct examples that show that this bound cannot in general be improved to $\gg \alpha \beta XY$. We also resolve the natural...

Let $S$ be a finite set of positive integers with largest element $m$. Let us randomly select a composition $a$ of the integer $n$ with parts in $S$, and let $m(a)$ be the multiplicity of $m$ as a part of $a$. Let $0\leq r<q$ be integers, with $q\geq 2$, and let $p_{n,r}$ be the probability that $m(a)$ is congruent to $r$ modulo $q$. We show that if $S$ satisfies a certain simple condition, then $\lim_{n\to \infty} p_{n,r} =1/q$. In fact, we show that an obvious necessary con...

In the theory of continued fractions, Zaremba's conjecture states that there is a positive integer $M$ such that each integer is the denominator of a convergent of an ordinary continued fraction with partial quotients bounded by $M$. In this paper, to each such $M$ we associate a regular sequence---in the sense of Allouche and Shallit---and establish various properties and results concerning the generating function of the regular sequence. In particular, we determine the mini...

Given a subset of the integers of zero density, we define the weaker notion of fractional density of such a set. It is shown how this notion corresponds to that of the Hausdorff dimension of a compact subset of the reals. We then show that a version of a theorem of {\L}aba and Pramanik on 3-term arithmetic progressions in subsets of the unit interval also holds for subsets of the integers with fractional density and satisfying certain Fourier-decay conditions.

We construct a set $A \subset \mathbf{N}$ such that one has $$ \sum_{n \in A: n \leq x} \frac{1}{n} = \exp\left(\left(\frac{1}{2}+o(1)\right) (\log\log x)^{1/2} \log\log\log x \right)$$ and $$ \frac{1}{(\sum_{n \in A: n \leq x} \frac{1}{n})^2} \sum_{n,m \in A: n < m \leq x} \frac{1}{\operatorname{lcm}(n,m)} \asymp 1$$ for sufficiently large $x$. The exponent $\frac{1}{2}$ can replaced by any other positive constant, but the growth rate is otherwise optimal. This answers in th...