## Elementary question about ‘Progressions avoiding sets’

For $y\in \mathbb{R}$ and $P \subset \mathbb{R}$, consider the distance $d(y,P) = \inf_{x\in P} |x-y|$.

Given arbitrary $\alpha, \beta, \gamma \in \mathbb{R}$, I am interested to know how to find the smallest $k \in \mathbb{N}$ s.t. $d(\alpha + \beta k,\mathbb{Z}) < \gamma$.

There are some special cases where the problem is easy to solve, but I'm not able to come up with an elegant (or attractively computable) answer to what seems like an elementary question.

-
 The keyphrase to search for is "inhomogeneous diophantine approximation." – Gerry Myerson Nov 30 2011 at 4:28 A related question is mathoverflow.net/questions/70035/… and there are some links there to related questions elsewhere and to other resources. – Gerry Myerson Nov 30 2011 at 4:31 Also related: mathoverflow.net/questions/22777/… – Gerry Myerson Nov 30 2011 at 4:35

I like this question and the answer, which doesn't seem to appear on either of the pages referenced above, comes from what is called the Ostrowski expansion of a real number (some references use other names for this expansion). This is an analogue of the base $p$ expansion which does for the $d(\cdot, \mathbb{Z})$ distance essentially the same thing that the base $p$ expansion does for the $p$-adic absolute value. I will explain it briefly here.

Assume that $\beta\in [0,1)$ is irrational, let $\beta=[a_0;a_1,\ldots]$ be the simple continued fraction expansion of $\beta$, and for each $n\ge 0$ let $p_n/q_n=[a_0;a_1,\ldots ,a_n]$ be the $n$th principal convergent. Also for each $n\ge 0$ let $$D_n=q_n\beta-p_n=(-1)^nd(q_n\beta ,\mathbb{Z}).$$ Then, modulo some minor technical details, there is an essentially unique expansion of the form $$\alpha=\sum_{n=0}^\infty b_{n+1}D_n$$ with $0\le b_{n+1}\le a_{n+1}$ for each $n$ (please note that I said "essentially unique", you can work out the details yourself and I will give a reference at the end of the post).

Next if $k\in\mathbb{N}$ then there is an essentially unique expansion of the form $$k=\sum_{n=0}^\infty c_{n+1}q_n,$$ with $0\le c_{n+1}\le a_{n+1}$ for each $n$.

Now since the quantity $d(\cdot,\mathbb{Z})$ is invariant under integer translation we have that $$d\left(\alpha-k\beta,\mathbb{Z}\right)=d\left(\alpha-k\beta+\sum_{n=0}^Nb_{n+1}p_n,\mathbb{Z}\right),$$ for any $N\ge 0$. Thus if $c_{n+1}=b_{n+1}$ for all $n< M$ (actually I think you technically have to assume $M\ge 4$ here) then it follows that $$d\left(\alpha-k\beta,\mathbb{Z}\right)=d\left(\sum_{n=M}^\infty (b_{n+1}-c_{n+1})D_n,\mathbb{Z}\right).$$

Finally since the quantities $D_m$ decrease at least exponentially it is not difficult to show that for $M\ge 4$ or $5$, $$d\left(\sum_{n=M}^\infty (b_{n+1}-c_{n+1})D_n,\mathbb{Z}\right)\asymp |b_{M+1}-c_{M+1}|\cdot |D_M|\asymp \frac{1}{q_M}.$$ The $\asymp$ sign here means that the left hand side is bounded above and below by positive constants times the right hand side.

So that in a nutshell is the answer to your question. You start with the Ostrowski expansion of $\alpha$ with respect to the continued fraction expansion of $\beta$, choose $M$ so that $1/q_M<\gamma$, and then any integer of the form $$k=\sum_{n=0}^{M-1}b_{n+1}q_m+\sum_{n=M}^Nc_{n+1}q_n,$$ with $0\le c_{n+1}\le a_{n+1}$ will be a solution to your inequality, modulo some universal constant and the minor technical points about the expansion that I mentioned above.

In particular to answer your question about the smallest integer which satisfies your inequality, assuming $\gamma$ is not too large (otherwise the problem is easy anyway), it will be given by choosing $M$ to the first integer such that $$k=\sum_{n=0}^{M-1}b_{n+1}q_m$$ satisfies the inequality. Also, everything here is explicitly computable from the continued fraction expansion of $\beta$.

For more technical details about the universal constants involved and about the restrictions on the digits necessary to get a unique Ostrowski expansion, see the book Continued Fractions by Rockett and Szusz. They call this the $t$-expansion of a real number.

-
 Thanks so much for the detailed answer and the reference. There is certainly a gap in my education where continued fractions are concerned! – TheNobleSunfish Dec 1 2011 at 1:36 A minor typo, I think, is that you've expanded $\beta$ instead of $\alpha$ in the second equation (understandable since after looking at some of the literature, I see I've reversed the conventional meanings of those symbols!) – TheNobleSunfish Feb 16 2012 at 1:41 You are correct- thank you, I will edit the post. – Alan Haynes Feb 16 2012 at 21:06