If $A\subset \Bbb Z$ with $|A| = n$, then there exists $t\in \Bbb Z\setminus p\Bbb Z$ such that $\phi(at/p) \le p^{-1/n}$ for all $a\in A$.

Question

Let $A \subset \Bbb Z$ with $|A| = n$, and $p$ be a prime. Consider $\phi:\Bbb R \to [0,\frac12]$ given by $\phi(x) = \min\{x-[x], 1 + [x] - x\}$, where $[\cdot]$ is the floor function. There exists $t \in \Bbb Z\setminus p\Bbb Z$ such that $\phi(at/p) \le p^{-1/n}$ for all $a\in A$.

$\phi(x)$ is just the distance of $x$ from the nearest integer, $[x]$ or $[x] + 1$. The problem gives pigeonhole principle vibes, but I'm yet to identify the pigeons and the holes.

Regardless, here's my attempt. I'll consider $n=1$ first. Let $A = \{a\}$ and $p$ be a prime. If $p \mid a$, then $a/p \in \Bbb Z$, and any choice of $t\in \Bbb Z\setminus p\Bbb Z$ works. Assume $p \not\mid a$. Then, we can express $a = pk + r$ for $1 \le r \le p -1$ and $k\in \Bbb Z$. Consequently, $$\phi\left(\frac{at}{p} \right) = \phi\left(kt + \frac{rt}{p} \right) = \phi\left(\frac{rt}{p} \right)$$

We want $t\in \Bbb Z$, $t\notin p\Bbb Z$ such that $\phi(rt/p) \le 1/p$. Now, $r/p$ is in $S_p := \{1/p, 2/p, \ldots, 1 - 1/p\}$ and the fractional part of $rt/p$ for $t\in \Bbb Z\setminus p\Bbb Z$ also lies in $S_p$. It shall suffice to show that for some $t\in \Bbb Z\setminus p\Bbb Z$, we have $\{rt/p\} = 1/p$ (or $1 - 1/p$.) This amounts to solving the congruence $rt \equiv 1 \bmod p$ for $t\in \Bbb Z\setminus p\Bbb Z$. Since $r \ne 0$, and $\Bbb Z/p\Bbb Z$ is a field ($p$ is prime), every non-zero element (in particular, $r$) is invertible. So we are done. Note that $(\Bbb Z/p\Bbb Z)\setminus\{0\} \subset \Bbb Z\setminus p\Bbb Z$ when viewed under the inclusion $\Bbb Z/p\Bbb Z \hookrightarrow \Bbb Z$.

I haven't been able to generalize this to $n\in \Bbb N$ yet, and I'd appreciate any hints or ideas to help me progress.

To use the pigeonhole principle, I suspect one should begin working with the cube $[0,1]^n$ and divide it into $p$ parts.

---

Notation:

• $\{x\}$ denotes the fractional part of $x \in \Bbb R$.

Answer 1

Let $d_n$ be the following metric on the torus $\mathbb T^n:=\mathbb R^n/\mathbb Z^n$: $$d_n(x,y)=\max_{1 \le i \le n} d_1(x_i,y_i)$$ where $$d_1(x_i,y_i):=\min_{m \in \mathbb Z} |x_i-y_i-m| \,.$$

Without loss of generality, we may assume that $A=\{a_1,\dots,a_n\} \subset \{0,1,\dots,p-1\}$. Let $v=(a_1/p,\dots,a_n/p) \in \mathbb T^n$.

For each $k \in \{0,1,\dots,p-1\}$, let $$Q_k:=\{x \in \mathbb T^n : d_n(x, kv) \le p^{-1/n}/2 \} $$ be the cube centered at $\, kv \in \mathbb T^n $ of side-length $p^{-1/n}$.

If these $p$ cubes were pairwise disjoint, then some $p$ open cubes containing the $Q_k$ would also be disjoint by compactness; this would yield a contradiction, since the volume of each $Q_k$ is $1/p$.

Therefore, there exist distinct $k,m \in \{0,1,\dots,p-1\}$ such that $Q_k \cap Q_m \ne \emptyset$, so $d_n(kv,mv) \le p^{-1/n}$ by the triangle inequality. Thus $\ell:=|k-m| \in \{1,\dots,p-1\}$ satisfies $$d_n(\ell v,\mathbf 0) \le p^{-1/n} \,,$$ as required.

Answer 2

Disclaimer: Partial solution (the result is shown with $2p^{-1/n}$ instead of $p^{-1/n}$, and in some special cases the correct bound is shown.)

We can reformulate the problem as follows:

Let $\mathbb{F}_p$ be the field with $p$ elements and view it as a subset of $\mathbb{Z}$ by sending a class $a+p\mathbb{Z}$ to the unique integer in it which is between $0$ and $p-1$. Let $v^0\in\mathbb{F}_p^n$ be a vector with only non-zero coordinates (otherwise we can reduce the dimension of the problem by just considering the non-zero ones), and let $V=\mathbb{F}_p\cdot v^0$ be its span. Also, consider the subset $$ S=\{0,\ldots,[p^{1-1/n}]\}\cup\{p-[p^{1-1/n}],\ldots,p-1\}\subseteq \mathbb{F}_p. $$ We want to show that the intersection $V^*\cap S^n$ is non-empty, where $V^*=V\setminus\{0\}$.

Notice that the only element of $V$ having a zero coordinate is $0$, so $V^*\subseteq (\mathbb{F}_p^\times)^n$. Let $\Delta:=[p^{1/n}]$ and divide $\mathbb{F}_p^\times$ into $\Delta$ intervals $I_1,\ldots,I_\Delta$ of length $L$ or $L+1$, where $L:=[(p-1)/\Delta]$. As $\Delta(L+1)>\Delta((p-1)/\Delta)=p-1$, at least one of the intervals has length $L$, and we may assume that it is $I_1$.

We obtain a partition of $(\mathbb{F}_p^\times)^n$ into $\Delta^n< p$ subsets by taking products of the above intervals. As $V^*$ has $p-1$ elements, either every element of the partition contains an element of $V^*$, or at least one of them contains two. In the first case we have in particular a $v\in V^*$ which is in $I_1^{n}$. Then all the coordinates of $v$ are inside $\{1,\ldots, L\}$, and thus $\phi(v_r/p)\leq L/p$ for all indices $r$.

In the second case, if $v',v''\in I_{i_1}\times\cdots\times I_{i_n}$ are two distinct elements of $V^{*}$ appearing in the same element of the partition, we consider $v:=v'-v''\in V^{*}$. Now let $r\in\{1,\ldots, n\}$ be some index, and write $I_{i_r}=\{a,a+1,\ldots,a+L\}$ (it might already stop at $a+L-1$ but in this case we are even better off). Then $v_r=v'_r-v''_r\in\{-L,\ldots,L\}$, and thus we see again $\phi(v_r/p)\leq L/p$.

Now unfortunately, it may happen that $L/p\geq p^{-1/n}$, for example if $p=2^n-1$ is a Mersenne prime. But one can show that $L/p\leq 2p^{-1/n}$ (at least when $p\geq 2^n$, but if $p\leq 2^n$ then $p^{-1/n}\geq 1/2$ so the bound is trivially satisfied), so we are only off by a factor of two. Also, if e.g. $\Delta^n=p-i$ for $i< \Delta$, then it is straightforward to see that $L/p\leq p^{-1/n}$.