Note on a problem of Sárközy on multiplicative representation functions

Yuchen Ding · 2025

Read Note on a problem of Sárközy on multiplicative representation functions by Yuchen Ding (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-09545.txt.

Introduction

Yuchen Ding settles a 2001 problem of Sárközy in a 2025 note. The question counts how the divisors of a set of whole numbers spread along two arithmetic progressions, and asks when the counts along the two can drift infinitely far apart. Ding classifies every choice of the four integers involved for which that unbounded gap is forced, no matter which infinite set is chosen.

Catalog record

CREATORYuchen Ding
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE10 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-09545

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Note on a problem of Sárközy on multiplicative representation functions Yuchen Ding Abstract . In this short note, we answer affirmatively a 2001 problem of Sárközy. 2010 Mathematics Subject Classification 11A05 Let \mathbb{N} be the set of natural numbers. In the unsolved problems list of Sárközy [ 1 , Problem 25] , he asked the following interesting question. Problem 1 (Sárközy) . For \mathcal{A}\subset\mathbb{N} and n\in\mathbb{N} let d(\mathcal{A},n)=\#\{a\in\mathcal{A}:a|n\}. Then is it true that for any infinite set \mathcal{A}\subset\mathbb{N} , |d(\mathcal{A},n+1)-d(\mathcal{A},n)| cannot be bounded? In this note, We answer it affirmatively. In fact, we will prove a stronger result. Theorem 1 . For any infinite set \mathcal{A}\subset\mathbb{N} and any nonzero k , we have \limsup_{n\rightarrow\infty}|d(\mathcal{A},n+k)-d(\mathcal{A},n)|=\infty. Proof. Suppose that \mathcal{A}=\{a_{1}<a_{2}<\cdots<a_{i}<\cdots\} . For any positive integer t let P_{t}=\prod_{1\leq i\leq t}a_{i}\quad\text{and}\quad\ell=\sup_{t\geq 1}\big\{\gcd(P_{t},k)\big\}. Then there is some fixed t_{0} so that \ell|P_{t_{0}} . For any positive integer m , one notes that \gcd\left(\frac{P_{t_{0}+m}}{\ell},\frac{k}{\ell}\right)=1. So, by Dirichlet’s theorem in arithmetic progressions there exists some prime p_{m}>\max\big\{\ell,|k|/\ell\big\} satisfying that \displaystyle p_{m}\equiv-\frac{k}{\ell}\ ({\rm{mod}}\ P_{t_{0}+m}/\ell). (1) Clearly, ( 1 ) implies \frac{P_{t_{0}+m}}{\ell}|(p_{m}+\frac{k}{\ell}) and hence P_{t_{0}+m}|(\ell p_{m}+k) , from which it follows \displaystyle d(\mathcal{A},\ell p_{m}+k)\geq t_{0}+m. (2) On the other hand, we have \displaystyle d(\mathcal{A},\ell p_{m})\leq 2\ell\leq 2|k| (3) since p_{m}>\ell . Moreover, p_{m}>|k|/\ell clearly implies \ell p_{m}+k>0 . Hence, we conclude from ( 2 ) and ( 3 ) that \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A},n+k)-d(\mathcal{A},n)| \displaystyle\geq\limsup_{m\rightarrow\infty}|d(\mathcal{A},\ell p_{m}+k)-d(\mathcal{A},\ell p_{m})| \displaystyle\geq\limsup_{m\rightarrow\infty}\Big(t_{0}+m-2|k|\Big)=\infty, proving our theorem. ∎ Let f_{\mathcal{A}}(n)=\min_{1\leq i\neq j\leq 3}\big\{|d(\mathcal{A},n+i)-d(\mathcal{A},n+j)|\big\}. I asked Prof. Yong-Gao Chen whether \limsup_{n\rightarrow\infty}f_{\mathcal{A}}(n)=\infty for any infinite \mathcal{A}\subset\mathbb{N} ? Immediately, he gave a negative answer by taking A=\{4m:m\in\mathbb{N}\} since at least two of n+1,n+2 and n+3 can not be divisible by 4 . Chen then suggested the following generalized problem. Problem 2 (Chen) . Determine the sufficient and necessary conditions of integers b,c,e and f sastisfying \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A},bn+c)-d(\mathcal{A},en+f)|=\infty for any infinite \mathcal{A}\subset\mathbb{N} . As a solution to problem 2 , we have the following theorem. Theorem 2 . Let b,c,e and f be integers. Then we have \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A},bn+c)-d(\mathcal{A},en+f)|=\infty (4) for any infinite \mathcal{A}\subset\mathbb{N} if and only if one of the following cases holds: I. b=c=e=0 and f\neq 0 ; or b=c=f=0 and e\neq 0 ; II. b=0 , e\neq 0 , and c=0 ; or b\neq 0 , e=0 , and f=0 . III. b=0 , e\neq 0 , c\neq 0 , and e|f ; or b\neq 0 , e=0 , f\neq 0 , and b|c ; IV. be\neq 0 , bf\neq ec , and b|c ; or be\neq 0 , bf\neq ec , and e|f . Remark. Clearly, Theorem 1 is contained in IV of Theorem 2 . Proof of Theorem 2 . Necessities. To prove the necessities, we separate them into a few cases. Case 1. b=e=0 . It is clear that the situation b=c=e=f=0 does not satisfy our requirement. Moreover, at least one of c and f equals zero. Otherwise, we have \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A},c)-d(\mathcal{A},f)|\leq|c|+|f|<\infty for any infinite \mathcal{A}\subset\mathbb{N} which is a contradiction. ( Case 1. corresponds with I.) Case 2. b=0 and e\neq 0 ; or b\neq 0 and e=0 . We only consider the case b=0 and e\neq 0 since the other situation will be treated similarly. In this case, c=0 is admissible since d(\mathcal{A},en+f)<\infty for all sufficiently large n as en+f\neq 0 for n>-f/e . We are left over to consider the situation b=0,e\neq 0 , and c\neq 0 . For any infinite \mathcal{A}\subset\mathbb{N} we clearly have d(\mathcal{A},c)\leq|c|. We are going to show e|f . Assume the contrary, i.e., e\nmid f . Take \mathcal{A}_{e}=\{|e|m:m\in\mathbb{N}\}\subset\mathbb{N} and then \limsup_{n\rightarrow\infty}d(\mathcal{A}_{e},en+f)=0. It follows that \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A}_{e},c)-d(\mathcal{A}_{e},en+f)|\leq|c|<\infty, which is a contradiction. ( Case 2. corresponds with II and III.) Case 3. be\neq 0 . In this case, we firstly show that c^{2}+f^{2}\neq 0 , i.e., at least one of c and f is nonzero. Otherwise, we choose a prime p_{0} so that p_{0}\nmid b and p_{0}\nmid e and take \displaystyle\mathcal{A}_{0}=\{p_{0}^{m}:m\in\mathbb{N}\}\subset\mathbb{N}. (5) Then we have \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A}_{0},bn)-d(\mathcal{A}_{0},en)| \displaystyle=\limsup_{n\rightarrow\infty}|d(\mathcal{A}_{0},n)-d(\mathcal{A}_{0},n)|=0, which is a contradiction. Next, we prove b|c or e|f . Assume the contrary. Then we may assume b=xb_{1},c=xc_{1},e=ye_{1} , and f=yf_{1} with b_{1},e_{1}\neq 1 , \gcd(b_{1},c_{1})=1 , and \gcd(e_{1},f_{1})=1 . We take \mathcal{A}_{b_{1},e_{1}}=\{(b_{1}e_{1})^{m}:m\in\mathbb{N}\}\subset\mathbb{N} . We claim that d(\mathcal{A}_{b_{1},e_{1}},bn+c) and d(\mathcal{A}_{b_{1},e_{1}},en+f) are bounded for all n , from which we have \limsup_{n\rightarrow\infty}|d(\mathcal{A}_{b_{1},e_{1}},bn+c)-d(\mathcal{A}_{b_{1},e_{1}},en+f)|<\infty, leading to a contradiction with ( 4 ). Actually, for all sufficiently large m if (b_{1}e_{1})^{m}|bn+c , then b_{1}|b_{1}n+c_{1} . This is a contradiction with \gcd(b_{1},c_{1})=1 and b_{1}>1 . Thus, the function d(\mathcal{A}_{b_{1},e_{1}},bn+c) is bounded for all n . The same argument yields that d(\mathcal{A}_{b_{1},e_{1}},en+f) is bounded for all n . We are left over to show bf\neq ec . Assume the contrary, i.e., \frac{c}{b}=\frac{f}{e}=g,\quad\text{say.} Since c^{2}+f^{2}\neq 0 , we have g\neq 0 . Moreover, g\in\mathbb{Z} since b|c or e|f . Then for \mathcal{A}_{0} as in ( 5 ) we also have \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A}_{0},bn+c)-d(\mathcal{A}_{0},en+f)| \displaystyle=\limsup_{n\rightarrow\infty}|d(\mathcal{A}_{0},b(n+g))-d(\mathcal{A}_{0},e(n+g))| \displaystyle=\limsup_{n\rightarrow\infty}|d(\mathcal{A}_{0},n+g)-d(\mathcal{A}_{0},n+g)|=0, which is a contradiction. ( Case 3. corresponds with IV.) Sufficiencies. We now turn to the proof of sufficiencies case by case. I. implies ( 4 ). Clearly. II. implies ( 4 ). Without loss of generality, we only consider the case b=0 , e\neq 0 , and c=0 since the other one can be proved similarly. We have d(\mathcal{A},en+f)<\infty for any n\neq-f/e since e\neq 0 . But d(\mathcal{A},0)=\infty for any n , from which (\ref{eq4}) clearly follows. III. implies ( 4 ). Without loss of generality, we only consider the case b=0 , e\neq 0 , c\neq 0 , and e|f since the other one can be proved similarly. We assume f=eh . For any positive integer t let P_{t}=\prod_{1\leq i\leq t}a_{i}. For any t there is a positive integer n_{t} so that n_{t}\equiv-h\ ({\rm{mod}}\ P_{t}), which means that P_{t}|e(n_{t}+h). In other words, d(\mathcal{A},n_{t}+h)\geq t . Hence, for sufficiently large t we have \displaystyle\limsup_{n\rightarrow\infty}|d(\mathcal{A},c)-d(\mathcal{A}_{g},en+f)| \displaystyle\geq\limsup_{t\rightarrow\infty}|d(\mathcal{A},c)-d(\mathcal{A},e(n_{t}+h))| \displaystyle\geq\limsup_{t\rightarrow\infty}(t-|c|)=\infty. IV. implies ( 4 ). Without loss of generality, we only consider the case be\neq 0 , bf\neq ec , and b|c since the other one can be proved similarly. Suppose that \mathcal{A}=\{a_{1}<a_{2}<\cdots<a_{i}<\cdots\} and c=bh . Since bf\neq ec , we have f-eh\neq 0 . For any positive integer t let P_{t}=\prod_{1\leq i\leq t}a_{i}\quad\text{and}\quad\ell=\sup_{t\geq 1}\big\{\gcd(eP_{t},f-eh)\big\}. Then there is some fixed t_{0} so that \ell|eP_{t_{0}} and \displaystyle P_{t_{0}}>|h|. (6) For any positive integer m , we have \gcd\left(\frac{eP_{t_{0}+m}}{\ell},\frac{f-eh}{\ell}\right)=1. Now, we will separate the arguments into two cases. Suppose first that e>0 . In this case, by Dirichlet’s theorem in arithmetic progressions there exists a prime \displaystyle p_{m}>\max\Big\{\frac{|f-eh|}{\ell},\ell\Big\} (7) satisfying that \displaystyle p_{m}\equiv\frac{f-eh}{\ell}\ ({\rm{mod}}\ eP_{t_{0}+m}/\ell), (8) which clearly means that \displaystyle\ell p_{m}-f+eh=eP_{t_{0}+m}q_{m} (9) for some integer q_{m} . Note that p_{m}>\frac{|f-eh|}{\ell} from ( 7 ). We have \ell p_{m}-f+eh>0 and hence P_{t_{0}+m}q_{m}>0 . Rearranging the terms in ( 9 ) leads to \displaystyle e(P_{t_{0}+m}q_{m}-h)+f=\ell p_{m}. (10) Moreover, one notes easily that \displaystyle b(P_{t_{0}+m}q_{m}-h)+c=bP_{t_{0}+m}q_{m}\equiv 0\ ({\rm{mod}}\ P_{t_{0}+m}). (11) From ( 10 ) and ( 11 ) we have \displaystyle d(\mathcal{A},e(P_{t_{0}+m}q_{m}-h)+f)=d(\mathcal{A},\ell p_{m}) (12) and \displaystyle d(\mathcal{A},b(P_{t_{0}+m}q_{m}-h)+c)\geq t_{0}+m. (13) Recall that p_{m}>\ell for any m from ( 7 ). Hence \displaystyle d(\mathcal{A},\ell p_{m})\leq 2\ell\leq 2|f-eh|. (14) Furthermore, from ( 6 ) we have P_{t_{0}+m}q_{m}-h>P_{t_{0}}-h>0. We conclude from ( 12 ), ( 13 ) and ( 14 ) that for sufficiently large m , \displaystyle\limsup_{n\rightarrow\infty}| \displaystyle d(\mathcal{A},bn+c)-d(\mathcal{A},en+f)| \displaystyle\geq\limsup_{m\rightarrow\infty}|d(\mathcal{A},b(P_{t_{0}+m}q_{m}-h)+c)-d(\mathcal{A},e(P_{t_{0}+m}q_{m}-h)+f)| \displaystyle=\limsup_{m\rightarrow\infty}|d(\mathcal{A},b(P_{t_{0}+m}q_{m}-h)+c)-d(\mathcal{A},\ell p_{m})| \displaystyle\geq\limsup_{m\rightarrow\infty}\big(t_{0}+m-2|f-eh|\big)=\infty. It remains to consider the case e<0 . In this case, we simply replace ( 8 ) by p_{m}\equiv-\frac{f-eh}{\ell}\

Read the complete text