Given a positive integer $\displaystyle n = \prod_{i=1}^s p_i^{\alpha_i}$, we write $\Omega(n)$ for the total number $\displaystyle \sum_{i=1}^s \alpha_i$ of prime factors of $n$, counted with multiplicity. Let $\lambda(n) = (-1)^{\Omega(n)}$ (so, for example, $\lambda(12)=\lambda(2^2\cdot3^1)=(-1)^{2+1}=-1$). Prove the following two claims: i) There are infinitely many positive integers $n$ such that $\lambda(n) = \lambda(n+1) = +1$; ii) There are infinitely many positive integers $n$ such that $\lambda(n) = \lambda(n+1) = -1$. (Romania) Dan Schwarz
Problem
Source:
Tags: function, number theory proposed, number theory
26.02.2011 19:54
i)Use the identity $a^2 -1 = (a-1)(a+1) $ we can construct solutions: $(15,16) $ --> $( {31^2} -1 , 31^2 )$ ---> $ ( (2 \times 31^2 -1)^2 -1 , (2 \times 31^2 -1)^2 )$ --- > ....
26.02.2011 20:45
ii) Choose an arbitrary $k$ such that $\lambda(k+1)= \lambda(k) =-1$ then look at the solutions of $(k+1)x^2 - ky^2 =1$ they are infinte and also $\lambda((ky^2 ))= \lambda((k+1)x^2) =-1$
26.02.2011 21:38
i) Let's assume that there are only finitely many integers n such that $\lambda(n)=\lambda(n+1)=1$ Then there exists an integer $N$ such that for all $a>N$, $\lambda(a)=1 \Longrightarrow \lambda(a+1)=-1$ Take some even $a>N$, then $(a-1,a+1)=1$, and as $\lambda(a^2)=1$, $\lambda(a-1)$ and $\lambda(a+1)$ have opposite signs. Continuing, we see that $\lambda(a+1)$ and $\lambda(a+3)$ have opposite signs, and we can do that until we reach $\lambda(a^2+1)$ Because of the assumption, we get $\lambda(a)=\lambda(a+2)=...=\lambda(a^2)=-1$, which is impossible, contradiction with the assumption. ii) Start as in i) Let $a$ be an odd number, $a>2N$, such that $\lambda(a)=-1$. Then if both $\lambda(a+1)$ and $\lambda(a-1)$ are 1, we get that $\lambda(\frac{a-1}2)=\lambda(\frac{a+1}2)=-1$, so we reach a contradiction.
26.02.2011 22:50
Of course, the question that immediately comes to mind is if one can find infinitely many consecutive triplets equal to $+1$ (respectively $-1$); then groups of four, etc., $k\geq 3$. We have no answer as of yet for this ...
27.02.2011 23:23
Solution to (1) Consider the sets $A=\{ m^2 -1 | m \in \mathbb{N} \}$ and $B = \{ m^2 | m \in \mathbb{N} \}$. We define a natural number $n$ to be good if it satisfies that $\lambda(n)=\lambda(n+1)=1$. If there are infinitely many $n \in A$ or $n \in B$ such that $n$ is good, then the claim is proven. Suppose that there are only finitely many good $n \in A$ and $n \in B$. Since $A$ and $B$ are infinite, this implies that there are infinitely many $m$ such that $\lambda(m^2 -1) = \lambda(m^2 +1)=-1$ since otherwise one of the numbers $m^2 -1$ or $m^2$ is a good number. However, this implies that $\lambda(m^4 -1) = \lambda(m^2-1) \lambda (m^2 +1) = 1$. Since $\lambda(m^4) = 1$, this implies that $m^4 -1$ is good. Since there are infinitely many $m$ satisfying this condition, there are infinitely many good numbers.
03.03.2011 22:44
Well, the problem can be killed by using a little bit of "theory". Pell"s equation $x^2-6y^2=1,$ which has infinitely many solutions implies the first part of the problem. Equation $3x^2-2y^2=1,$ which also has infinitely many solutions takes care of the second part.
03.03.2011 22:55
Indeed, those equations are verbatim listed among the alternative proofs in the official solution
20.03.2011 04:26
i) Note that $\lambda(x^2) = 1$ for all integers $x$. Now note that either there exist infinitely many integers $\alpha$ such that $\lambda(\alpha^2 - 1) = 1$ or there don't. If infinitely many such $\alpha$ exist, then we are done. If only finitely many such $\alpha$ exist, then there exists a positive integer $M$ such that for all $\alpha > M$, we have $\lambda(\alpha^2 - 1) = -1$. This would imply that for all $\alpha > M$, we have $\lambda(\alpha - 1) = -\lambda(\alpha + 1)$, since $\lambda$ is clearly a multiplicative function. Then after a certain point, the values of $\lambda$ would cycle $1,1,-1,-1,1,1,-1,-1,\dots$ etc., so we are done. ii) Note that $\lambda(px^2) = -1$ for all integers $x$ and primes $p$. Now note that there are infinitely many integer solutions in integers $(r,s)$ to the equation $3s^2 - 2r^2 = 1$; if $(r,s)$ is a solution, then $(4r + 5s, 5r + 6s)$ is a solution, and $(1,1)$ is a solution. Thus we are done.
20.03.2011 04:29
Another solution to part i: Observe that $\lambda$ is multiplicative. Consider the numbers $2^{2^n} - 1, 2^{2^n}, 2^{2^n} + 1$. If $\lambda(2^{2^n} + 1)$ is 1 for infinitely many positive integers $n$, then $\lambda(2^{2^n}) = \lambda(2^{2^n} + 1) = 1$ holds for infinitely many $n$. Otherwise, we may suppose that for all sufficiently large $n$, $\lambda(2^{2^n} + 1) = -1$. Hence, for any sufficiently large $n$, if $\lambda(2^{2^n} - 1) = 1$, since $\lambda(2^{2^n}) = 1$, we are done; otherwise, we have $\lambda(2^{2^{n+1}} - 1) = \lambda(2^{2^n} - 1) \lambda(2^{2^n} + 1) = -\lambda(2^{2^n} - 1) = 1 = \lambda(2^{2^{n+1}})$, so we are done.
03.03.2012 20:36
Otherwise : i) We observe that $\lambda(a^2)=\lambda (6a^2)=1$ and we use the Pell's equation.
30.10.2014 19:00
i)First,assume contrary,now we have that for some $N$,it holds that if $a>N$ we have that if $f(a)=1$ then $f(a+1)=-1$ and opposite.Now,just pick ann odd integer such $f(n)=1$(it is obvious that it exists) such that is larger than $2N$.Now,we have that $f(n+1)=-1$ and $f(n-1)=-1$,so $f(n+1/2)=f(n-1/2)=1$,so we are finished. ii) Just pick an odd n such that $f(n)=-1$ and the rest is the same.
21.01.2015 21:11
Assume (i) is false. Then for $n>N$, $\lambda(n)=\lambda(n+1)=1$ is false, so for $n>2N$ even, $\lambda(n)=\lambda(n+2)=-1$ is false. Take any $\lambda(n+1)=1$, this implies an immediate contradiction. (ii) is same. This is completely trivial
21.01.2015 21:51
Not so fast ... you only know $\lambda(n)$ and $\lambda(n+2)$ are not both equal to $-1$ for even $n$'s (thus at least one is equal to $1$). Who tells you that you can find some $\lambda(n+1)=1$ for an even $n$? For example, the alternating sequence, starting from an even value of $n>2N$, given by $1,-1,1,-1,1,-1,\ldots$ has no $\lambda(n) = \lambda(n+1) =1$, nor $\lambda(n) = \lambda(n+2) = -1$ for $n$ even. The problem is not that trivial.
21.01.2015 23:31
mavropnevma I thought about addressing this in my first post but I thought it looked nicer as a one-liner Just take $ n+1 = x^2 $ with $ x $ odd. For the case where we prove (ii), take $n+1= 3x^2$ with $x$ odd.
05.09.2015 02:26
Cute problem but a little easy for RMM P4 a.) take $n=m^2$ and let $m^2+1=10d^2$ This is a Pell type equation and kills a.) b.) take $n=2m^2$ let $2m^2+1=3t^2$. This again is a Pell type equation killing b.)
19.08.2021 18:59
For part a) take $x^2-6y^2=1$ and for part b) $3x^2-2y^2=1$
19.04.2023 11:05
a) If $(2k-1)^2$ and $(2k+1)^2$ do not satisfy the condition then $ \lambda (\frac{(2k-1)^2+1}{2} \frac{(2k+1)^2+1}{2})$ is even. Thus $4k^4$ satisfies the conditions.
11.05.2023 06:03
Say that a positive integer $n$ is red if $\lambda(n)=1$, and blue otherwise. Then, the problem is asking to prove that there are infinitely many consecutive red pairs and consecutive blue pairs. Claim: For any positive integer $n$, at least one of $(n^2-1,n^2)$, $(n^2,n^2+1)$, or $(n^4-1,n^4)$ is a consecutive red pair. Clearly, $n^2$ and $n^4$ are both red. Then, if either one of $n^2-1$ and $n^2+1$ are red, then the claim would be true. However, if they are both blue, then their product, $n^4-1$, would be red, so the claim is still true. This claim clearly solves part (i). For part (ii), assume FTSOC there exists $m$ such that all blue numbers past $m$ are isolated. Then, pick $n>777770m$ such that $n$ is odd and blue (e.g. pick a sufficently large power of 3 that is not a power of 9). Then, $n-1$ and $n+1$ are both red by our FTSOC claim. However, this means that $(n-1)/2$ and $(n+1)/2$ are both blue, and they are consecutive integers, which contradicts our FTSOC claim since they are both still larger than $m$. Hence, we are done.
11.12.2023 23:15
First note that there are infinitely many values of $n$ such that $\lambda(n)=\lambda(n+1)$. Indeed, if starting from some point the values of $\lambda$ alternated, then $\lambda(x)$ would be determined by the parity of $x$ (for $x$ large enough), which is an obvious contradiction (odd squares and even squares both give a $\lambda$ value of $1$). We can thus find infinitely many $m$ such that $\lambda(m-1)=\lambda(m+1)$ (multiplying by $2$ the claim above), so that $\lambda(m^2-1)=\lambda(m^2)=1$. This proves (i) Now we deal with part (ii) : take some $a$ divisible by $6$. If $\lambda(a^2+2)$ (resp. $\lambda(a^2+3)$) is equal to $1$, then $-1=\lambda(a^2/2)=\lambda(a^2/2 +1)$ (resp. $-1=\lambda(a^2/3)=\lambda(a^2/3 +1)$. If not, then $-1=\lambda(a^2+2)=\lambda(a^2+3)$. This proves (ii). $\blacksquare$
13.12.2023 14:11
mavropnevma wrote: Of course, the question that immediately comes to mind is if one can find infinitely many consecutive triplets equal to $+1$ (respectively $-1$); then groups of four, etc., $k\geq 3$. We have no answer as of yet for this ... This is a fairly state-of-the-art question. For $k=3$ Hildebrand [1] showed that all eight patters on $\pm 1$ occur infinitely often and much later Matomaki et al. [2] have shown that these patters occur with a positive frequency (I am talking about the generalised problem, but it turns our that the hardest part of the proof is dealing with the runs in question, namely $k$ consecutive 1's or -1's). Unless some major advancements have been made in the last 5-ish years, it is still unkown whether all the patters for $k=4$ are present infinitely often. Of course, it is expected that for any $k{}$, any pattern of signs occurs infinitely often - even more so, these patterns occur with equal frequencies - as stated by Chowla's conjecture. I'm not entirely sure, but there are some connections between Chowla's conjecture and the Riemann Hypothesis, so perhaps it is completely out of reach as of now, let alone for an olympiad problem. [1] A. Hildebrand – On consecutive values of the Liouville function. Enseign. Math. (2) 32 (1986), 219–226. [2] K. Matomaki, M. Radziwill and T. Tao – Sign patterns of the Mobus and Liouville functions. Preprint, arXiv:1509:01545. Edit: I just realised that the second paper I linked wasn't even published at the time of the competition. How time flies...