(1) Let $a,b$ be coprime positive integers. Prove that there exists constants $\lambda$ and $\beta$ such that for all integers $m$, $$\left| \sum\limits_{k=1}^{m-1} \left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\} - \lambda m \right| \le \beta$$ (2) Prove that there exists $N$ such that for all $p>N$ (where $p$ is a prime number), and any positive integers $a,b,c$ positive integers satisfying $p\nmid (a+b)(b+c)(c+a)$, there are at least $\lfloor \frac{p}{12} \rfloor$ solutions $k\in \{1,\cdots,p-1\}$ such that $$ \left\{\frac{ak}{p}\right\} + \left\{\frac{bk}{p}\right\} + \left\{\frac{ck}{p}\right\} \le 1 $$
Problem
Source: China TST 2023, Test 1, Problem 3
Tags: China TST, number theory
15.03.2023 01:05
05.04.2023 12:30
For(1),We will show that$\lambda = \int_{0}^{1}\left \{ ax \right \} \left \{ bx \right \}dx$satisfied. In fact,we would show that$\left [ \frac{ab\left ( k-1 \right ) }{m} ,\frac{abk}{m} \right ]\cap \mathbb{Z}= \emptyset $, then we are done. This$\Longleftrightarrow\left \{ \frac{ak}{m} \right \} \left \{ \frac{bk}{m} \right \} -m\int_{\frac{k-1}{m} }^{\frac{k}{m} }\left \{ ax \right \}\left \{ bx \right \} dx=\mathrm {O}\left ( \frac{1}{m} \right )$ and$\Longleftrightarrow \sup_{x\in \left [ \frac{k-1}{m} ,\frac{k}{m} \right ]}\left \{ ax \right \} \left \{ bx \right \} -\inf_{x\in \left [ \frac{k-1}{m} ,\frac{k}{m} \right ]}\left \{ ax \right \} \left \{ bx \right \} =\mathrm {O} \left ( \frac{1}{m} \right )$ It's obviously right. $\blacksquare$
12.04.2023 08:37
The original problem (2) from 数之谜 is that "for large enough prime $p$,...". Is the problem still correct after removing this condition?
28.04.2023 11:42
This problem is similar to modern art, in the sense that I have no clue what the point of this problem even is. 1) Trivial by combining Lagrange interpolation on each of the finite cases of m modulo ab. 2) We proceed by forgetting part 1 and using the power of combinatorics instead. First, notice that we can rewrite the fractional parts by: $$px \leq ak < px + p, py \leq bk < py + p, pz \leq ck < pz + p, px+py+pz \leq ak+bk+ck \leq px+py+pz + p$$. This rewrites as (always implied from here on that we choose maximal x, y, z): $$\frac{x}{k} \leq \frac{a}{p}, \frac{y}{k} \leq \frac{b}{p}, \frac{z}{k} \leq \frac{c}{p}, \frac{a+b+c}{p} \leq \frac{x+y+z+1}{k}$$ This condition is true if and only if $k$ is a solution. Now notice that if there are three values of $k$ that sum to $p$ for which this fails, then since $\min(\frac{a}{b}, \frac{c}{d}, \frac{e}{f}) \leq \frac{a+c+e}{b+d+f} \leq \max(\frac{a}{b}, \frac{c}{d}, \frac{e}{f})$ in general, it follows that we would obtain $$a-1 \leq x_1+x_2+x_3+1 \leq a, b-1 \leq y_1+y_2+y_3+1 \leq b, c-1 \leq z_1+z_2+z_3+1 \leq c, (x_1+y_1+z_1+1)+(x_2+y_2+z_2+1)+(x_3+y_3+z_3+1) < a+b+c$$ This means it cannot be the case that all of $x_1+x_2+x_3 = a-1, y_1+y_2+y_3 = b-1, z_1+z_2+z_3 = c-1$ is true. Also for two values of $k$ that sum to $p$ for which this fails, the same logic gives contradiction unless $x_1+x_2+1 = a, y_1+y_2+1 = b, z_1+z_2+1 = c$ which is forced. Thus it follows that if there are three values of $k$ which fail that sum to $2p$, there is a corresponding triple of $k$ summing to $p$, whose values of $k$ must either be solutions or satisfy the exception described above. Notice that now we wish to investigate whether for given values of $k_1, k_2, k_3$ which all are values of $k$ that fail, whether $x_1+x_2+x_3 = a - 2$ or $a - 1$. Notice that it suffices to determine $\lfloor k_1 \cdot \frac{a}{p} \rfloor + \lfloor k_2 \cdot \frac{a}{p} \rfloor + \lfloor k_3 \cdot \frac{a}{p} \rfloor$, and thus the sum is $a - 1$ if and only if $\sum \{k_i \cdot \frac{a}{p} \} \leq 1$, which happens if an only if a majority of the $k_i$ satisfy $\{k_i \cdot \frac{a}{p} \} \leq \frac{1}{2}$. We say such a value of $k_i$ is an $a$-small value of $k$, and define the same property for $b, c$. Now notice we can WLOG $a = 1$ with varying $b, c$ such that $p \nmid b+c$ and $2 \leq b, c \leq p - 2$ and $b \neq c$. We now wish to search for values of $k$ which are $a$-small, $b$-small and $c$-small. We proceed with double counting. We wish to find $k$ such that $\{\frac{k}{p}\} < \frac{1}{2}$, $\{\frac{bk}{p}\} < \frac{1}{2}$. and $\{\frac{ck}{p}\} < \frac{1}{2}$. We rephrase the question to be finding residues modulo $p$ such that they lie in the intersection of the sets $\{1, 2, \ldots, \frac{p-1}{2}\}, b \cdot \{1, 2, \ldots, \frac{p-1}{2}\}, c \cdot \{1, 2, \ldots, \frac{p-1}{2}\}$. Each residue, when paired with its negative, is either in all sets / no sets or in two/one set. In the latter, the pair will generate one incidence of being both $x$-small and $y$-small, and the former will generate three such incidences. Now to find how many incidences there are, notice that in any series $n \{1, 2, \ldots, \frac{p-1}{2} \}$ where $n \neq p - 1$, if we color each element with whether it is less than or greater than $\frac{p}{2}$, we notice that the biggest advantage of one color over the other is $k+1 + \frac{\frac{p-1}{2}}{2k+1}$ where $k$ is the $\lceil \frac{\frac{p-1}{2}}{n} \rceil$. Since $k$ cannot be greater than $\frac{1}{4} \frac{p-1}{2}$ if $n \neq p-1$, this advantage is maximized when $k = 1$ giving $2+\frac{p-1}{6}$. Thus the minimum number of incidences between two such series is $\frac{p-1}{2} - (2+\frac{p-1}{6}) = \frac{p-1}{3} - 2$. Thus the total number of incidences over all three series (from $n = 1, b, c$) is at least $p-7$. Now this means the double count implies that there are at least $\frac{p-7 - \frac{p-1}{2}}{2} = \frac{p - 1}{4} - 3$ such $k$. We say these values of $k$ are heavy values. Now suppose there are $s$ heavy values which are not solutions. Then applying our lemma against numbers summing to $p$ yields that for any two heavy values $x, y$, it follows that we must have $p - x - y$ be a solution, since the $a$-small condition implies that any heavy value is less than $\frac{p}{2}$. Thus the sumset of the remaining heavy values to themselves, after being subtracted from $p$, are all solutions. So by Cauchy-Davenport theorem, assuming the claim is false, we must have that $2s-1 \leq \lfloor \frac{p}{12} \rfloor$. Thus the rest of the heavy values must be solutions, so we obtain that the total number of solutions is at least $\frac{p-1}{4} - 3 - \lfloor \frac{1+ \frac{p}{12}}{2} \rfloor$. This is at least $\lfloor \frac{p}{12} \rfloor$ for all $p > 25$, so it suffices to only check the values of $p = 13, 17, 19, 23$. In all of these cases, it suffices to prove the existence of a single heavy value, as no matter what logic is applied, a heavy value implies the existence of at least one solution somewhere. It is easy to manually check that a heavy value always exists in these four cases: For $p = 13$ one can manually check all $25$ relevant combinations of $b, c$. For $p = 17$ one can manually check the sets of form $n \cdot \{1, 2, \ldots, \frac{p-1}{2}\}$ to notice they all have intersection size at least $3$ with $\{1, 2, \ldots, \frac{p-1}{2}\}$. Hence the total incidence count is at least $9$, which is more than $8$, implying the existence of a heavy value. For $p = 19$ our formula gives that the minimum number of incidences between two sets is $4$, so since total is $12 > 9$, this implies the existence of a heavy value. For $p = 23$ our formula gives that the minimum number of incidences between two sets is $6$, so since total is $18 > 11$, this implies the existence of a heavy value. Thus all cases are resolved.
29.04.2023 07:05
PureRun89 wrote: The original problem (2) from 数之谜 is that "for large enough prime $p$,...". Is the problem still correct after removing this condition? My bad, fixed
15.05.2023 00:43
14.06.2023 17:59
There are tow things that i dont understand them Firstone that about $1_{ \{ax\} > \{bx\}}$ Secondly about this function $Cov(X,X)$
14.06.2023 18:46
Can anyone explain??
14.06.2023 18:59
$f(x)=1_{ \{ax\} > \{bx\} } $ is an indicator variable. $f(x)=1$ if $\{ ax \} > \{ bx \}$ and $f(x)=0$ otherwise. For random variables X, Y, $$Cov(X,Y)=\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y]$$ ALSO: in my solution, for $x\in \mathbb{R}$, we define $||x|| = \min\{ \{x\}, 1-\{x\}\}$, i.e. $||x||$ is the distance between $x$ and the closest integer to $x$.
18.06.2023 21:13
Is there another solution???
19.06.2023 15:27
Any solution???
01.07.2023 06:52
This problem is quite difficult.I think it is proposed by wangbing
01.07.2023 08:41
Can someone post the post the official solution, from the author ?
05.07.2023 06:13
There must be an official solution.
16.07.2023 08:51
I met the author at IMO and I know the main steps of our solutions are the same.
16.07.2023 13:28
what techniqe this is and where can someone learn this
18.07.2023 15:59
My solution employs many techniques; the second moment method, the dirichlet approximation, and recursion.
24.07.2023 18:10
CANBANKAN wrote: My solution employs many techniques; the second moment method, the dirichlet approximation, and recursion. Would you write it pls??
25.07.2023 07:08
CANBANKAN wrote:
They are all here
15.10.2023 10:53
Here is the solution from proposer, I will post the solution for Part 2 when I understand it. Part 1. Let $f_m(a,b)=\sum\limits_{k=1}^{m-1} \left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\},$ $f(a,b)=\int_{0}^m\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}dk.$ The idea is to calculate the difference. $$f_m(a,b)-f(a,b)=\sum\limits_{k=1}^{m-1} \left(\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}-\int_{k-\frac 12}^{k+\frac 12}\left\{ \frac{at}{m} \right\}\left\{ \frac{bt}{m} \right\}dt\right)-\left(\int_{0}^{\frac 12}\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}dk+\int_{m-\frac 12}^{m}\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}dk\right).$$For $\forall 1\le k\le m-1,$ define $A_k=\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}-\int_{k-\frac 12}^{k+\frac 12}\left\{ \frac{at}{m} \right\}\left\{ \frac{bt}{m} \right\}dk.$ If there exists $i\in[k-\frac 12,k+\frac 12]$ such that $\left\{ \frac{ai}{m} \right\}=0$ or $\left\{ \frac{bi}{m} \right\}=0,$ there are at most $a+b$ of them. Now suggest there doesn't exist such ${i}.$ Then for $\forall k-\frac 12\le t\le k+\frac 12,$ $\exists |\delta |\le\frac 1{2m},$ $$\left\{ \frac{at}{m} \right\}\left\{ \frac{bt}{m} \right\}=\left(\left\{ \frac{at}{m}\right\}+\frac{a\delta}m \right)\left(\left\{ \frac{bt}{m}\right\}+\frac{b\delta}m \right).$$Therefore $$\begin{aligned}A_k &=\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}-\int_{k-\frac 12}^{k+\frac 12}\left(\left\{ \frac{at}{m}\right\}+\frac{a\delta}m \right)\left(\left\{ \frac{bt}{m}\right\}+\frac{b\delta}m \right)dt\\ &=ab\left(\frac 1{ab}\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}-\int_{-\frac 12}^{\frac 12}\left(\frac 1a\left\{ \frac{at}{m}\right\}+\frac{\delta}m \right)\left(\frac 1b\left\{ \frac{bt}{m}\right\}+\frac{\delta}m \right)d\delta\right)\\ &\le ab\int_{-\frac 12}^{\frac 12}\frac{\delta ^2}{m^2}d\delta =-\frac 1{12m^2}. \end{aligned}$$Then $\left|f_m(a,b)-f(a,b)\right|\le \left|m\cdot\frac 1{12m^2}\right|+a+b+1\le 2(a+b).$ Now we only need to calculate f(a,b). $$\begin{aligned} \int_{0}^m\left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\}dk &=m\int_{0}^1\{ak\}\{bk\}dk =m\sum\limits_{t=0}^{ab-1}\int_{\frac{t}{ab}}^{\frac{t+1}{ab}}\{ak\}\{bk\}dk\\ &=\frac{m}{ab}\sum\limits_{t=0}^{ab-1}\int_{0}^{1}\left\{\frac{a(t+\delta)}{ab}\right\}\left\{\frac{b(t+\delta)}{ab}\right\}d\delta\\ &=\frac{m}{ab}\sum\limits_{t=0}^{ab-1}\int_{0}^{1}\left(\left\{\frac{t}{b}\right\}+\frac{\delta}b\right)\left(\left\{\frac{t}{a}\right\}+\frac{\delta}a\right) d\delta\\ &=\frac{m}{ab}\sum\limits_{t=0}^{ab-1}\int_{0}^{1}\left(\frac{\delta ^2}{ab}+\delta\left(\frac 1a\left\{\frac{t}{b}\right\}+\frac 1b\left\{\frac{t}{a}\right\}\right)+\left\{\frac{t}{a}\right\}\left\{\frac{t}{b}\right\}\right) d\delta\\ &=\frac{m}{ab}\sum\limits_{t=0}^{ab-1}\left(\frac 1{3ab}+\frac 1{2a}\left\{\frac{t}{b}\right\}+\frac 1{2b}\left\{\frac{t}{a}\right\}+\left\{\frac{t}{a}\right\}\left\{\frac{t}{b}\right\}\right)\\ &=\frac{m}{ab}\left(\frac 13+\frac a{2a}\sum\limits_{j=0}^{b-1}\frac jb+\frac b{2b}\sum\limits_{i=0}^{a-1}\frac ia+\sum\limits_{i=0}^{a-1}\frac ia\sum\limits_{j=0}^{b-1}\frac jb\right)\\ &=\frac{m}{ab}\left(\frac 13+\frac{b-1}4+\frac{a-1}4+\frac{(a-1)(b-1)}4\right)\\ &=\frac m{ab}\left(\frac 1{12}+\frac{ab}4\right)=\left(\frac 14+\frac 1{12ab}\right)m. \end{aligned}$$Therefore we let $\lambda =\frac 14+\frac 1{12ab},\beta =2(a+b)$ and we are done$.\blacksquare$