What is an upper bound of $(x - r)_{\pmod d} + (x + r)_{\pmod d}$ in terms of $x$ and $d$?

Question

Let $x, r, d \in \Bbb{Z}$, $x,d \geq 1$ and $r \geq 0$. I'm wondering what an upper bound for the expression:

$$ f(x,r,d) = (x - r)_{\pmod d} + (x + r)_{\pmod d} $$

is in terms of $x, d$ only. I know that $(2x)_{\pmod d}$ is a lower bound and I can prove that easily using modular arithmetic.

The quantities $(x \pm r)_{\pmod d}$ are simply the least non-negative residue of $x \pm r$ in $\{0, \dots, d-1\} \subset \Bbb{Z}$, modulo $d$.

I would like to think that $2(x)_{\pmod d} + \text{ something}$ is an upper bound, and to prove that, suppose that:

$$ (x + r)_{\pmod d} + (x - r)_{\pmod d} \gt 2(x)_{\pmod d} + s $$

where $s = \text{something}$. Then we would have:

$$ (x + r)_{\pmod d} + (x-r)_{\pmod d} = 2(x)_{\pmod d} + s + k $$

for some $1 \leq k \leq (d - 1)$? For the proof by contradiction to go through we need $k \leq (d - 1)$, but I can't as in the lower bound case seem to show that $k$ is necessarily $\leq (d-1)$.

Answer 1

If I understand it correctly, a more rigorous formulation of your question is: for any integers $d\ge1$ and $x,$ find an upper bound for the set $$S_{x,d}:=\{f(x,r,d)\mid r\in\Bbb Z\}.$$ Moreover, if you only wanted an upper bound, $2(d-1)$ would be an easy one. Let us instead find the maximum (and the minimum, which is not always $(2x)_{\pmod d}$).

Assume wlog that $$x,r\in[0,d).$$ Then:

• $(x-r)_{\pmod d}=\begin{cases}x-r&\text{if }r\le x\\x-r+d&\text{if }r>x\end{cases}$
• $(x+r)_{\pmod d}=\begin{cases}x+r&\text{if }r<d-x\\x+r-d&\text{if }r\ge d-x\end{cases}$

so

$f(x,r,d)=\begin{cases}\text{if }x<d-x:&\begin{cases}\text{if }x<r<d-x:&2x+d\\\text{else}:&2x\end{cases}\\\text{if }x\ge d-x:&\begin{cases}\text{if }d-x\le r\le x:&2x-d\\\text{else}:&2x\\\end{cases}\end{cases}$

The first subcase of the first case never occurs if $x=d-x-1.$ Therefore, $$\forall x\in[0,d)\quad S_{x,d}=\begin{cases}\{2x,2x+d\}&\text{if }x<(d-1)/2\\\{2x\}=\{d-1\}&\text{if }x=(d-1)/2\\ \{2x-d,2x\}&\text{if }x\ge d/2.\end{cases}$$

Since $(2x)_{\pmod d}$ is equal to $2x$ if $0\le x<d/2$ and to $2x-d$ if $d/2\le x<d,$ coming back to the general case of an arbitrary integer $x,$ the previous trichotomy becomes:

$$\forall x\in\Bbb Z\quad S_{x,d}=\begin{cases}\{d-1\}&\text{if }(x)_{\pmod d}=\frac{d-1}2,\\\{(2x)_{\pmod d},(2x)_{\pmod d}+d\}&\text{else.}\end{cases}$$