Given positive integers $a,b,c$ which are pairwise coprime. Let $f(n)$ denotes the number of the non-negative integer solution $(x,y,z)$ to the equation $$ax+by+cz=n.$$Prove that there exists constants $\alpha, \beta, \gamma \in \mathbb{R}$ such that for any non-negative integer $n$, $$|f(n)- \left( \alpha n^2+ \beta n + \gamma \right) | < \frac{1}{12} \left( a+b+c \right).$$
Problem
Source: 2021 China TST, Test 2, Day 1 P3
Tags: algebra, number theory, Diophantine equation
21.03.2021 18:42
Let $\zeta_a=e^{2\pi i/a}$ etc., then all the $\zeta_a^j\,(1\leq j\leq a-1)$ and $\zeta_b^j\,(1\leq j\leq b-1)$ and $\zeta_c^j\,(1\leq j\leq c-1)$ are different, so we can calculate \[\frac{1}{(1-x^a)(1-x^b)(1-x^c)}=\frac{\lambda_2}{(1-x)^3}+\frac{\lambda_1}{(1-x)^2}+\frac{\lambda_0}{1-x}+\sum_{j=1}^{a-1}\frac{\rho_j(a)}{1-\zeta_a^jx}+\sum_{j=1}^{b-1}\frac{\rho_j(b)}{1-\zeta_b^jx}+\sum_{j=1}^{c-1}\frac{\rho_j(c)}{1-\zeta_c^jx},\]where $\lambda_i\,(0\leq i\leq 2)$ are constants depending only on $(a,b,c)$, and \[\rho_j(a)=\lim_{x\to\zeta_a^{-j}}\frac{1-\zeta_a^jx}{(1-x^a)(1-x^b)(1-x^c)}=\frac{1}{a}\frac{1}{(1-\zeta_a^{-jb})(1-\zeta_a^{-jc})},\]and similar for $\rho_j(b)$ and $\rho_j(c)$. Now the $n$-th power coefficient \[[x^n]\bigg(\frac{\lambda_2}{(1-x)^3}+\frac{\lambda_1}{(1-x)^2}+\frac{\lambda_0}{1-x}\bigg)=\lambda_2\binom{n+2}{2}+\lambda_1\binom{n+1}{1}+\lambda_0=\alpha n^2+\beta n+\gamma,\]so we just need to estimate the $n$-th power coefficient \[[x^n]\bigg(\sum_{j=1}^{a-1}\frac{\rho_j(a)}{1-\zeta_a^jx}+\sum_{j=1}^{b-1}\frac{\rho_j(b)}{1-\zeta_b^jx}+\sum_{j=1}^{c-1}\frac{\rho_j(c)}{1-\zeta_c^jx}\bigg):=\Delta_n\]and prove $|\Delta_n|<\frac{1}{12}(a+b+c)$. Clearly \[\Delta _n=\frac{1}{a}\sum_{j=1}^{a-1}\frac{\zeta_a^{jn}}{(1-\zeta_a^{-jb})(1-\zeta_a^{-jc})}+(\mathrm{two\ other\ similar\ terms)},\]so it suffices to show that \[\bigg|\sum_{j=1}^{a-1}\frac{\zeta_a^{jn}}{(1-\zeta_a^{-jb})(1-\zeta_a^{-jc})}\bigg|\leq\frac{a^2}{12}.\]By Cauchy-Schwartz the above is bounded by \[\bigg(\sum_{j=1}^{a-1}|1-\zeta_a^{-jb}|^{-2}\bigg)^{1/2}\bigg(\sum_{j=1}^{a-1}|1-\zeta_a^{-jc}|^{-2}\bigg)^{1/2}=\frac{1}{4}\bigg(\sum_{j=1}^{a-1}\frac{1}{\sin^2(\pi jb/a)}\bigg)^{1/2}\bigg(\sum_{j=1}^{a-1}\frac{1}{\sin^2(\pi jc/a)}\bigg)^{1/2},\]moreover when $1\leq j\leq a-1$ varies, $\{jb\}$ and $\{jc\}$ each runs over a complete residue class modulo $a$ (except $0$), so it suffices to show that \[\sum_{j=1}^{a-1}\frac{1}{\sin^2(\pi j/a)}<\frac{a^2}{3}.\]However by considering the roots of the polynomial \[P_a(\sin x)=\frac{\sin(ax)}{\sin x}\mathrm{\ for\ }a\mathrm{\ odd},\quad P_a(\sin x)=\frac{\sin(ax)}{\sin x\cos x}\mathrm{\ for\ }a\mathrm{\ even},\]and using Vieta's theorem, we can easily calculate \[\sum_{j=1}^{a-1}\frac{1}{\sin^2(\pi j/a)}=\frac{a^2-1}{3}.\]The proof is now complete.
21.03.2021 22:47
Nice problem
02.05.2021 16:26
I think there's an elementary proof to this problem. There are three big steps in this solution. Step1 : Calculating $f(n)$ Notice that the number of $(x,y)$ with the condition $ax+by=n$ is $\frac{n-as-bt}{ab}+1$ for smallest nonnegative integers $s,t$ satisfying $as+bt\equiv n(mod ab)$ Using this one can calculate the $f(n)$, which is $\sum_{i=0}^{\lfloor\frac{c}{n}\rfloor}\frac{n-ap_i-bq_i-ci}{ab}+1$ where $p_i,q_i$ is the smallest nonnegative integers satisfying $ap_i+bq_i\equiv n-ci(mod ab)$. With $n=cq+r, q=aq_1+r_1=bq_2+r_2$, we can conclude that $f(n)=\frac{n^2}{2abc}+\frac{n(a+b+c)}{2abc}+\frac{(b-1)r_2}{2b}+\frac{(a-1)r_1}{2a}+\frac {r(c-a-b)}{2abc}- \frac{1}{a}\sum_{i=0}^{r_1}q_i-\frac{1}{b}\sum_{i=0}^{r_2}p_i- \frac{r^2}{2abc}$ Now setting $\alpha$ as $\frac{1}{2abc}$, $\beta$ as $\frac{a+b+c}{2abc}$, we have to show the existence of $\gamma$ with the condition $\left| \gamma -(\frac{(b-1)r_2}{2b}+\frac{(a-1)r_1}{2a}+\frac {r(c-a-b)}{2abc}- \frac{1}{a}\sum_{i=0}^{r_1}q_i-\frac{1}{b}\sum_{i=0}^{r_2}p_i- \frac{r^2}{2abc})\right|<\frac{a+b+c}{12}$ Step2 : $\left| \frac{(a-1)(r_1+1)}{2a}-\frac{1}{a}\sum_{i=0}^{r_1}q_i \right|<\frac{a^2-1}{8a}$ For $r_1$, $\sum_{i=0}^{r_1}q_i$ is maximum $(a-1)+...+(a-r_1-1)$, minimum $0+...+r_1$ Hence $\left| \frac{(a-1)(r_1+1)}{2a}-\frac{1}{a}\sum_{i=0}^{r_1}q_i \right|\leq \frac{(r_1+1)(a-1-r_1)}{2a}\leq \frac{a^2-1}{8a}$ Same for $b$. Step3 : Conclusion WLOG assume $a\leq b\leq c$, since if $a=b=c=1$, it's trivial, assume $c\geq2$ 3.1 If $c<a+b$, the value $\frac{(c-a-b)r}{2abc}-\frac{r^2}{2abc}$ moves in range which has size smaller than $\frac{1}{2a}+\frac{1}{2b}$, and hence there exists a constant $\gamma _1$ such that $\left|\frac{(c-a-b)r}{2abc}-\frac{r^2}{2abc}-\gamma _1\right|<\frac{1}{4a}+\frac{1}{4b}$ ($\frac{(c-a-b)r}{2abc}-\frac{r^2}{2abc}$ has maximum when $r=0$, minimum when $r=c-1$, and it's difference is $\frac{ac+bc+1-a-b-c}{2abc}<\frac{1}{2a}+\frac{1}{2b}$) Also if $a=1,c\leq b$ then $b=c$, which is a contraction. Hence $a\geq 2$, then $a<b<c$. Then $2c\geq a+b+3> a+b+\frac{3}{a}+\frac{3}{b}$, which is equal to $\frac{1}{4a}+\frac{1}{4b}<\frac{1}{8a}+\frac{1}{8b}+\frac{2c-a-b}{24}$ Now by Step 2 and this, there exists $\gamma$ such that $\left| \gamma -(\frac{(b-1)r_2}{2b}+\frac{(a-1)r_1}{2a}+\frac {r(c-a-b)}{2abc}- \frac{1}{a}\sum_{i=0}^{r_1}q_i-\frac{1}{b}\sum_{i=0}^{r_2}p_i- \frac{r^2}{2abc})\right|$ $<\frac{a^2-1}{8a}+\frac{b^2-1}{8b}+\frac{1}{8a}+\frac{1}{8b}+\frac{2c-a-b}{24} = \frac{a+b+c}{12}$ 3.2 If $c\geq a+b$, the value $\frac{(c-a-b)r}{2abc}-\frac{r^2}{2abc}$ moves in range which has size smaller than $\frac{(a+b+c-2)^2}{8abc}$, and hence there exists a constant $\gamma _1$ such that $\left|\frac{(c-a-b)r}{2abc}-\frac{r^2}{2abc}-\gamma _1\right|\leq \frac{(a+b+c-2)^2}{16abc}$ (The same as 3.1, maximum at $r=\frac{c-a-b}{2}$) We need to show that $\frac{(a+b+c-2)^2}{16abc}<\frac{1}{8a}+\frac{1}{8b}+\frac{2c-a-b}{24}$ to conclude 3.2 as 3.1. (For $ab>1$) As $\frac{(a+b+c-2)^2}{16abc}=\frac{(a+b)^2}{16abc}+\frac{a+b}{8ab}+\frac{c}{16ab}-\frac{a+b+c-1}{4abc}$ $\leq\frac{c^2}{16abc}+\frac{a+b}{8ab}+\frac{c}{16ab}-\frac{a+b+c-1}{4abc}=\frac{a+b}{8ab}+\frac{c}{8ab}-\frac{a+b+c-1}{4abc}$, Let's show that $\frac{c}{8ab}-\frac{a+b+c-1}{4abc}<\frac{2c-a-b}{24}$ for $ab>1$ If $ab\geq 3$, $\frac{c}{8ab}-\frac{a+b+c-1}{4abc}<\frac{c}{8ab}\leq \frac{c}{24}\leq \frac{2c-a-b}{24}$ If $a=1,b=2$, $\frac{c}{8ab} -\frac{a+b+c-1}{4abc}< \frac{c}{16}-\frac{1}{8}<\frac{c}{12}-\frac{1}{8}=\frac{2c-a-b}{24}$ Now for $a=b=1$, as $r_1=r_2=0$, it suffices to show that there exists $\gamma$ such that $\left| \gamma -\frac{r(c-a-b)}{2abc}-\frac{r^2}{2abc}\right| <\frac{a+b+c}{12}$ Same as 3.2's $\gamma _1$, take this $\gamma$ to satisfy $\left|\frac{(c-a-b)r}{2abc}-\frac{r^2}{2abc}-\gamma \right|\leq \frac{(a+b+c-2)^2}{16abc}=\frac{c}{16}<\frac{a+b+c}{12}$ Now we've ended all the cases, and now our proof is completed