Function that forms an Arithmetic Sequence

Question

I've been working on this problem for a while:

Let $n > 2$ be an integer. Let $f$ be a function from the set of all integers to itself with the following property: If the integers $a_1, a_2, a_3, \dots, a_n$ form an arithmetic progression, then the numbers $f(a_1), f(a_2), \dots f(a_n)$ form an arithmetic progression in some order (that's possibly constant). Determine all values $n$ such that the only functions $f$ with the above property are the functions in this form: $f(x)=bx+c$, where $b$ and $c$ are integers.

My work is most likely trivial, but I wrote $a_1, a_2, \dots a_n$ as $a_1, a_1+x, a_1+2x, \dots, a_1+(n-1)x$. Then, applying $f(x)=bx+c$ to each term in the sequence, I got that the values of the sequence were $$ba_1+c, b(a_1+x)+d, \dots, b(a_1+(n-1)x)+d.$$ However, I'm unable to make more progress.

Thanks for any form of help!

Answer 1

(Fill in the gaps as needed, especially when it says "Show that". If you're stuck, explain what you've tried.)

Claim: For $n$ prime, the function $f(a) = ( a \mod n )$ satisfies the conditions.

Proof: Show that any AP of length $n$, taken modulo $n$ (prime), is either

1. A constant sequence, or
2. $\{ 1 , 2, \ldots , n-1, n \}$.

In either case, $ f(a_i)$ forms an AP. $_\square$

---

Suppose that for some $n$, we had such a non-linear function $f(x)$.

Suppose that the function is not injective.

Let $k$ be the minimum positive integer such that there exists $ |a-b| = k$ and $ f(a) = f(b)$. WLOG, let $ a < b$.

• Case 1: $k < n$.
  Show that $ f(x) $ is a constant, which is a contradiction.
• Case 2: $ k > n$.
  Consider the AP's $ \{ f(a+i + j)\}_{j=0}^{n-1}$ going from $ i = 0$ to $ i = k+1 - n > 1$.
  Since $ f(a) \neq f( a +n)$, and $ \{ f(a+j)_{j=0}^{n-1} \}, \{ f(a+1+j)_{j=0}^{n-1} \}$ both form an non-constant AP, show that $ \{ f(a), f(a + n) \} $ must be the minimum and maximum of $ \{ f(a+j) \} _{j=0}^n$.
  WLOG, let $ f(a) < f(a+n)$, so $ f(a)$ is the minimum and $f(a+n)$ is the maximum.
  Applying the same logic to $ f(a+1) \neq f(a+1+n)$, $\{ f(a+1), f(a +1+ n) \} $ must be the minimum and maximum of $ \{ f(a+j) \} _{j=1}^{n+1}$. Since $f(a+1) < f(a+n)$, hence $f(a+1)$ is the minimum and $f(a+1+n)$ is the maximum, so $ f(a+n) < f(a+n+1)$.
  We thus get the chain of inequalities $ f(a) < f(a+n) < f(a+n+1) < \ldots < f(a+k)$, contradicting the choice of $k$. Thus, no such function is possible.
• Case 3: $ k = n$.
  Show that for any non-trivial divisor $ d \mid n$, $ 1 < d < n$ , we have $ f(a) = f( a + \frac{k}{d} ) $. Thus, if $n$ is composite, no such function is possible.

Hence, a non-injective non-linear function could exist only if $k=n$ and $n$ is prime.

Now, suppose that the function is injective.
Using the same argument as in Case 2, show that

Assuming $f(0 ) < f(n)$,
We thus get the chain of inequalities $ f(n) < f(n+1) < f(n+2) < \ldots $.
Similarly, we get the chain of inequalities $ \ldots < f(n-2) < f(n-1 ) < f(n) $.

(Show that) $f(x) = f(0) + x ( f(1) - f(0) ) $ is a linear function.

Hence, a non-linear function could exist only if $k=n$ and $n$ is prime. We have shown above that such a solution exists.

---

For prime $n$, we have the following solution:

Let $ g: \mathbb{Z_n} \rightarrow \mathbb{Z_n}$ be a bijection. Then, $ f(a) = b \times g ( a \mod{n} ) + c $ satisfies the conditions. The solution at the top is the identity $ g(a \mod{n} ) = a \mod {n}$ and $b = 1, c = 0 $.
I believe that in Case 3, using the technique similar to Case 2, we can show that $f(x+n) = f(x)$ for all $x$, from which the solution follows.