A lower bound on the count of numbers in an arithmetic progression which are close to an integer For a real number $x$ let
$$
 d(x) = | x -\lfloor x+1/2 \rfloor | = \min \{ |x-k| : k \in \Bbb Z \}
$$
denote the distance of $x$ to the closest integer. I have the following

Conjecture: Let $x \in \Bbb R$ and $n$ be a positive integer. Then
$$ d(j \cdot x) \le \frac 13 $$ holds for at least $\lfloor n/2 \rfloor$ of the numbers $j \in \{ 1, 2, \ldots n \}$.

In other words, at least half of the numbers in the arithmetic progression $x, 2x, \ldots, nx$ are “close to an integer” in the sense that $|jx -k| \le 1/3$ for some $k \in \Bbb Z$.
I have verified the conjecture numerically for all $n \le 20$, and also for some larger values such as $n=80$ (see below). What I am looking for is a proof.
Motivation: This is motivated by a recent question:

For $x \in \Bbb R$ and a positive integer $n$ is
$ \sum_{j=1}^{n+1} |\cos(j \cdot x) | \ge \frac n 4 $.

A proof (using trigonometric identities, sum formula, and estimates) has already been given. If the above conjecture is true then it would allow for a very simple proof:
For at least $\lfloor (n+1)/2 \rfloor$ of the $j \in \{ 1, 2, \ldots, n+1\}$ is
$$
 d(j \cdot \frac{x}{\pi}) \le \frac 13 \implies \left| j \cdot x - k \pi \right| \le \frac \pi 3 \text{ for some integer $k$} \\
 \implies |\cos(j \cdot x) | \ge \frac 12
$$
and therefore
$$
\sum_{j=1}^{n+1} |\cos(j \cdot x) | \ge \left\lfloor \frac{n+1}2 \right\rfloor \frac 1 2 \ge \frac n 4 \, .
$$
Some thoughts on the conjecture:

*

*All functions $x \mapsto d(j \cdot x)$ are $1$-periodic and even, therefore it suffices to show the conjecture for $0 \le x \le 1/2$.


*For $x = 0$ is $d(j \cdot x) = 0 < \frac 13$ for all $j \in \{ 1, 2, \ldots n \}$.


*For $x= 1/2$ is $d(j \cdot x) = 1/2$ if $j$ is odd, and $d(j \cdot x) = 0$ if $j$ is even, so that $d(j \cdot x) \le  1/3$ holds for exactly  $\lfloor n/2 \rfloor$ of the numbers $j \in \{ 1, 2, \ldots n \}$. This shows that the bound $\lfloor n/2 \rfloor$  (if valid) would be best possible.


*If suffices to prove the conjecture for even $n$.


*For very small values of $n$ the conjecture can be verified directly. For example, if $0 \le x \le 1/3$ then $d(x) \le 1/3$, and if $1/3 \le x \le 1/2$ then $2/3 \le x \le 1$, so that $d(2x) \le 1/3$. This shows that at least one of the distances $d(x), d(2x)$ is $\le 1/3$, and proves the conjecture for $n=2$ and $n=3$. For $n=4$ it already gets nasty to distinguish all possible cases.
I have verified the conjecture numerically for many values of $n$, using Maxima/wxMaxima on a Mac. With
d(x) := abs(x-floor(x+1/2));
c(n, x) := sum(if d(j*x) <= 1/3 then 1 else 0, j, 1, n);

I plotted the value of $c(n, x)$ for $x \in \left[0, 1\right]$, and all results confirmed the conjecture.
Some examples: For $n=10$:

For $n=80$:

 A: For $t\in\mathbb{R}$ let $d(t)$ be the distance from $t$ to the nearest integer.

Fix $x,n$ where $x\in\mathbb{R}$ and $n$ is a positive integer.

Let $J=\{1,...,n\}$ and let $A,B$ be given by
\begin{align*}
A&=\,\left\{j\in J{\,{\large{\mid}}\,}d(jx)\le{\small{\frac{1}{3}}}\right\}\\[4pt]
B&=\,\left\{j\in J{\,{\large{\mid}}\,}d(jx) > {\small{\frac{1}{3}}}\right\}\\[4pt]
\end{align*}
Claim:$\;|A|\ge\lfloor{\large{\frac{n}{2}}}\rfloor$.

Proof:

If $B={\large{\varnothing}}$, the truth of the claim is immediate, so assume $B\ne{\large{\varnothing}}$.

Let $m=\min(B)$, and for each $k\in\{0,...,m-1\}$, let $A_k,B_k$ be given by
\begin{align*}
A_k&=\,\{a\in A{\,\mid\,}a\equiv k\;(\text{mod}\;m)\}\\[4pt]
B_k&=\,\{b\in B{\,\mid\,}b\equiv k\;(\text{mod}\;m)\}\\[4pt]
\end{align*}
It's easily seen that for $s,t\in\mathbb{R}$, if both
$d(s) > {\large{\frac{1}{3}}}$
and
$d(t) > {\large{\frac{1}{3}}}$,
then
$d(s+t) < {\large{\frac{1}{3}}}$.

Then since $m\in B$, it follows that between any two consecutive elements of $B_k$, there is at least one element of $A_k$.

Explanation: If $b,b'\in B_k$ with $b < b'$, then $b+m\le b'$, but since $m\in B$, it follows that $b+m\in A$, hence we get $b < b+m < b'$ and $b+m\in A_k$.

Hence we get $|A_k|\ge |B_k|-1$ for all $k$.

In particular we have $|A_0|\ge |B_0|-1$.

But for $1\le k\le m-1$, noting that $k\in A_k$, we get the improvement $|A_k|\ge|B_k|$, hence
\begin{align*}
|A|=\;&
\sum_{k=0}^{m-1} |A_k|
\\[4pt]
=\;&
|A_0|+\sum_{k=1}^{m-1} |A_k|
\\[4pt]
\ge\;&
\Bigl(|B_0|-1\Bigl)+\sum_{k=1}^{m-1} |B_k|
\\[4pt]
=\;&
|B|-1
\\[4pt]
\end{align*}
so then
\begin{align*}
&
|A|\ge|B|-1
\\[4pt]
\implies\;&
2|A|\ge|A|+|B|-1
\\[4pt]
\implies\;&
2|A|\ge n-1
\\[4pt]
\implies\;&
|A|\ge\frac{n-1}{2}
\\[4pt]
\implies\;&
|A|\ge\left\lfloor{\frac{n}{2}}\right\rfloor
\\[4pt]
\end{align*}
as claimed.
