17
$\begingroup$

Let $f:\mathbb{N}\to\mathbb{N}$ be a function such that $f(a)+b$ is a square iff $f(b)+a$ is also a square. Show that $f$ is injective. Note that, in this context, $0\notin\mathbb{N}.$

Clearly, $f$ can't be a constant function. Suppose there exists some $c\in\mathbb{N}$ such that $f(n)=c$ for all $n\in\mathbb{N}.$ Pick some natural number $m>\sqrt{c}.$ Now, $f(n)+m^2-c$ is a square for all $n\in\mathbb{N}.$ This implies that $n+f(m^2-c)=n+c$ is a square for all $n\in\mathbb{N}.$ Clearly, this can't hold.

I haven't made much progress apart from this. I tried the usual method of assuming $f(a)=f(b)$ and then somehow getting $a=b,$ but that didn't work.

If we assume $f(a)=f(b)$ but $a≠b,$ we can deduce that $|b-a|$ must be a difference of squares. I don't know where to go from here.

PS: I don't know about the validity of the question, but I haven't been able to construct such a function that's also non-injective. In fact, the only function I can think of that satisfies this is the identity function.

$\endgroup$
12
  • 2
    $\begingroup$ Or the identity function plus an arbitrary constant. $\endgroup$
    – Lieven
    Commented May 26 at 16:14
  • 1
    $\begingroup$ Is $0 \in \mathbb{N}$ in your definition of the natural numbers? $\endgroup$
    – Marco
    Commented May 26 at 16:17
  • 2
    $\begingroup$ What is the source of this problem? $\endgroup$ Commented May 26 at 16:23
  • 2
    $\begingroup$ @aqualubix this seems to be an interesting (but difficult) question (+1)... $\endgroup$ Commented May 26 at 16:28
  • 1
    $\begingroup$ As a suggestion: perhaps it's easier to prove that $f$ must be the identity (up to an additive constant). Of course, I'm not certain that stronger claim is even true, but it would be interesting to see a different example. $\endgroup$
    – lulu
    Commented May 26 at 16:40

3 Answers 3

8
$\begingroup$

Call a value $c\in\mathbb N$ popular if there exist $a,b\in\mathbb N$ with $a\neq b$ and $f(a)=f(b)=c$. Our aim is to show that no number is popular.

Call an unordered pair $\{x,y\}$ of (not necessarily distinct) integers intertwined if $f(m^2-x)=y$ whenever $m>\sqrt x$ and $f(n^2-y)=x$ whenever $n>\sqrt y$. We first learn some things about intertwined pairs.


Observation. Any two intertwined pairs are either identical or disjoint.

Lemma 1. There exist finitely many intertwined pairs.

Proof. The idea is to make $m_1^2-x_1$ and $m_2^2-x_2$ agree for $x_1$ and $x_2$ in (separate) intertwined pairs. Suppose for the sake of contradiction that there are infinitely many intertwined pairs. Then there exists some residue class modulo $4$ which contains infinitely many elements of intertwined pairs. Let $x_1$ be the smallest element of an intertwined pair in this class, and let $x_2$ be another element of an intertwined pair in this class with $x_2>100x_1$. Suppose $x_1$ and $x_2$ are in pairs $(x_1,y_1)$ and $(x_2,y_2)$, respectively. Define $$m_1=\frac{x_2-x_1}4-1\qquad m_2=\frac{x_2-x_1}4+1.$$ We may compute that $m_2^2-m_1^2=x_2-x_1$. Additionally, we have $m_1>23x_1>\sqrt x_1$ and $m_2>\frac{x_2}5>\sqrt{x_2}$. So, by the fact that $x_1$ and $x_2$ lie in intertwined pairs, we have $$y_1=f(m_1^2-x_1)=f(m_2^2-x_2)=y_2.$$ However, by our observation, $y_1\neq y_2$. This gives the desired contradiction. $\square$

Lemma 2. If $(x,y)$ is intertwined, then $f^{-1}(x)=\{n^2-y\colon n>\sqrt y\}$.

Proof. Suppose $f(r)=x$. Then $f(r)+m^2-x$ is a square for all $m>\sqrt x$, so $r+f(m^2-x)=r+y$ is a square. $\square$


We now relate popular numbers to intertwined pairs.

Lemma 3. Any popular number is part of some intertwined pair.

Proof. Suppose that $c$ is popular, so that $f(a)=f(b)=c$ with $a<b$. For each $m>\sqrt c$, $f(a)+(m^2-c)$ is a perfect square, so $a+f(m^2-c)$ is a perfect square too. Similarly, $b+f(m^2-c)$ is a perfect square. These are distinct perfect squares with difference $b-a>0$; there are only finitely many such pairs of perfect squares, so we conclude that $$\big\{f(m^2-c)\colon m\in\mathbb N,m>\sqrt c\big\}$$ is finite.

So, there is some $y$ which occurs as $f(m^2-c)$ for infinitely many $m$. Let $S$ be the set of $m$ with $f(m^2-c)=y$. For $m\in S$, we have that $n^2-y+f(m^2-c)$ is a perfect square for all $n>\sqrt y$, so $$f(n^2-y)+m^2-c$$ is a perfect square for every positive integer $n>\sqrt y$. Let $\Delta_n=f(n^2-y)-c$; we have that $m^2+\Delta_n$ is a square for infinitely many $m$. This implies that $\Delta_n=0$. So, $f(n^2-y)=c$ for all $n>\sqrt y$.

Now, for each $m>\sqrt c$, $m^2-c+f(n^2-y)$ is a square for all large $n$, so $f(m^2-c)+n^2-y$ is a square for all large $n$. We conclude by the same logic as above that $f(m^2-c)=y$ for all $m>\sqrt c$. So $(c,y)$ is an intertwined pair, as desired. $\square$

Corollary 1. There are only finitely many popular numbers.

Corollary 2. There exist infinitely many integers $t$ for which none of $f(t),f(t+1),f(t+2),f(t+3)$ are popular.

Proof. If the popular numbers are enumerated as $\{x_1,\ldots,x_k\}$, then $f(t)$ is not popular as long as $t+x_i$ is not a square for each $i$. Let $X=\max_{1\leq i\leq k}x_i$. As long as $n>X+10$, say, the numbers $\{f(n^2),f(n^2+1),f(n^2+2),f(n^2+3)\}$ cannot be popular, as $n^2+3+X<(n+1)^2$. $\square$


Corollaries 1 and 2 get us rather close to showing injectivity: very few outputs are popular, and those outputs do not correspond to too many inputs. For the remainder of the proof, we denote by $\mathcal S$ the set of positive integers $t$ for which $f(t)$ is popular, and we let $\mathcal T=\mathbb N\setminus \mathcal S$.

Lemma 4. Suppose $x$ is popular. Then, for all but finitely many $t\in\mathcal T$, $f(t)-x\equiv 2\pmod 4$.

Proof. Let $y$ be so that $\{x,y\}$ are intertwined. We must show that there are finitely many $t\in\mathcal T$ with $f(t)-x$ odd, and finitely many $t\in\mathcal T$ with $4\mid f(t)-x$. By the definition of $\mathcal T$, it suffices to show that there are finitely many values $u=f(t)$ which satisfy these properties (since each of these values is attained as $f(t)$ for exactly one $t\in\mathcal T$).

Suppose $u-x\not\equiv 2\pmod 4$ and $u=f(t)$ for some $t\in\mathcal T$. We claim that $u\leq x+4\sqrt x+4$. Indeed, if not, we can write $u=x+2m+1$ or $u=x+4m+4$ (depending on whether $u-x$ is odd or a multiple of $4$) for some $m>\sqrt x$. Now, $m^2-x+u$ is a square, so $t+f(m^2-x)=t+y$ is a square; call it $n^2$. Then, since $t=n^2-y$, we have $u=f(t)=x$, a contradiction. $\square$

We are now ready to finish the argument. Suppose that there is a popular number $c$, and let $X$ be the maximum of the popular numbers. This lemma gives us the existence of some positive integer $N$ and some residue class $r_0\pmod 4$ so that, if $t\in\mathcal T$ and $t>N$, then $f(t)\equiv c+2\pmod 4$. Fix any $t\in\mathcal T$ with $t>N$, $f(t)>X$, and $t\equiv -c\pmod 4$, guaranteed to exist by Corollary 2. Now, let $u>10f(t)+\sqrt{f(t)+N}$. We have that $u^2-f(t)+f(t)$ is a square, so $$t+f(u^2-f(t))$$ is a square. However, $u^2-f(t)>N$, so if $u^2-f(t)\in\mathcal T$ we must have $f(u^2-f(t))\equiv c+2\pmod 4$. Since $t\equiv -c\pmod 4$, this cannot happen. So, we must have $u^2-f(t)\in\mathcal S$ for all $u>\sqrt{f(t)+N}$. By Lemma 1, this implies that $u^2-f(t)=v^2-x$ for some popular $x$. However, by our choice of $u$, $u^2-f(t)+x$ lies strictly between $(u-1)^2$ and $u^2$, a contradiction. This finishes the proof.

$\endgroup$
2
$\begingroup$

This is a partial answer.

For all $a\in\mathbb{N}$, define $S(a):=\mathbb{N}\cap \{n^2-a:n\in\mathbb{N}\}$. I show that if $f(a)=f(b)$ for some $a\neq b$, then $f$ must be constant on $S(f(a))$. That is, there exists some $c\in\mathbb{N}$ such that $f(n^2-f(a))=c$ for all $n\in\mathbb{N}$ with $n^2> f(a)$.

Claim: 1 Let $a\in\mathbb{N}$. Then $f$ restricts to a function $S(f(a))\to S(a)$.

Proof: Let $a\in\mathbb{N}$ and let $b:=n^2-f(a)\in S(f(a))$. Then $f(a)+b=n^2$ is a perfect square, so there exists an $m\in\mathbb{N}$ with $f(b)+a=m^2$. Hence, $f(b)=m^2-a\in S(a)$. $\square$

Claim 2 Let $a,b\in\mathbb{N}$ be distinct. Then $S(a)\cap S(b)$ is finite.

Proof: WLOG, assume $a>b$. For any element $n^2-a=m^2-b\in S(a)\cap S(b)$ we obtain a factor $d:=m+n$ of $a-b$ and for any factor $d'\mid a-b$ we obtain at most one element of the intersection $S(a)\cap S(b)$, given by $n'^2-a=m'^2-b$, where $$n':=\frac12(d'+\frac{a-b}{d'})\quad\text{and}\quad m':=\frac12(d'-\frac{a-b}{d'}).$$ Since $a-b$ has finitely many factors, we are done. $\square$


Assume for the sake of contradiction that there exist distinct $a,b\in\mathbb{N}$ with $f(a)=f(b)$. By the first claim, $f$ restricts to a function $S(f(a))\to S(a)\cap S(b)$, but this intersection is finite by the second claim, while $S(f(a))$ is infinite. Thus, there exist a $c\in\mathbb{N}$ and a sequence $\{c_k\}_{k\ge 0}$ in $S(f(a))$ such that $f(c_k)=c$ for all $k\ge 0$.

Now, let $\ell\in S(c)$ such that $c+\ell$ is a perfect square. Then $f(c_k)+\ell$ is a perfect square for all $k\ge 0$, so $f(\ell)+c_k$ is a perfect square for all $k$, so $c_k\in S(f(\ell))\cap S(f(a))$ for all $k$. By the second claim, we see that $f(\ell)=f(a)$ for all $\ell\in S(c)$.

We claim that $f(d)=c$ for all $d\in S(f(a))$. To prove this, let $d\in S(f(a))$ and let $n^2-c\in S(c)$, then $f(n^2-c)+d=f(a)+d$ is perfect square, so $f(d)-c+n^2$ is as well, for all sufficiently large $n$. This implies $f(d)=c$, which proves the claim.

$\endgroup$
0
2
$\begingroup$

Suppose that $a< b$ and $f(a)=f(b)$. Then for all $n^2>f(a)$ we have that $f(n^2-f(a))+a$ and $f(n^2-f(a))+b$ are squares since $f(a)+n^2-f(a)=n^2$ and $f(b)+n^2-f(a)=n^2$. There are only finitely many $d$ such that $d+a$ and $d+b$ are both squares, since if $C>D$ are in $\mathbb{N}$, then $C^2-D^2\geq C^2-(C-1)^2=2C-1$, thus $C^2-D^2=b-a$ only for finitely many $C,D$. Thus, there exists $c\in\mathbb{N}$ such that the set $S=\{s\in\mathbb{N}\mid f(s^2-f(a))=c\}$ is infinite. Choose $m$ such that $m^2>c$. Then $f(m^2-c)+s^2-f(a)$ is a square for all $s\in S$, since $f(s^2-f(a))+m^2-c=m^2$, but this would imply that $f(m^2-c)-f(a)=C^2-D^2$ for infinitely many pairs $C,D$ and we have already seen that this is impossible.

$\endgroup$
1
  • $\begingroup$ Why can't $f(m^2-c)$ equal $f(a)$ for all $m>\sqrt c$? $\endgroup$ Commented May 27 at 20:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .