1
$\begingroup$

Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a nonempty subset $ I$ of $ \{1,2,...,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer. - (Problems from the book, chapter 17)

This is a solution I have found on AoPS:

Solution a la Vess: Consider $ \prod_j(e^{2\pi i\frac{x-a_j}{b_j}}-1)=\sum_I\pm e^{2\pi i (A_I x+B_I)}$. Looking at the left hand side, we see that its average over $ \mathbb Z$ (understood as $ \lim_{N\to\infty}\frac1{2N+1}\sum_{-N}^N$) is $ 0$. Looking at the right hand side, we see that if no $ A_I$ with $ I\ne\varnothing$ is an integer, then it is $ (-1)^n$.

Is this answer correct? If so, how can I understand this solution ? What is $A_I$ and $B_I$ ? Are there any other solutions for this problem ?

$\endgroup$
  • 2
    $\begingroup$ This is a result of Ming-Zhi Zhang in 1989. $\endgroup$ – Zhi-Wei Sun Dec 23 '18 at 13:19
  • $\begingroup$ The use of abbreviations, possibly known in one given country, makes it a bit tricky to track the quotation. $\endgroup$ – YCor Dec 23 '18 at 13:45
  • 1
    $\begingroup$ @YCor if you are talking about AoPS, this is probably artofproblemsolving.com $\endgroup$ – Fedor Petrov Dec 23 '18 at 14:31
  • $\begingroup$ A related comment. It also turns out that, the smallest $n$ for which an $n$-covering system (namely, system of $n$-congruences, $x\equiv a_i\pmod{b_i}$ with $b_1<\cdots<b_n$ such that, every $k\in\mathbb{Z}$ obeys at least one of them) is precisely 5, and an old Turkish olympiad problem. $\endgroup$ – kawa Dec 29 '18 at 21:02
5
$\begingroup$

This is a result of Ming-Zhi Zhang in 1989 [J. Sichuan Univ. (Nat. Sci. Ed.) 26(1989), Special Issue 185-188]. For my simple proof and extensions of this result, one may consult my talk, the survey Problems and Results on Covering Systems and my 1995 paper in Acta Arith.

$\endgroup$
  • $\begingroup$ I don't like a book using a known result as an exercise without proper citation. $\endgroup$ – Zhi-Wei Sun Dec 23 '18 at 13:32
  • $\begingroup$ But the book might just ignore that the result was known. It's also plausible that it was initially proved before 1989. $\endgroup$ – YCor Dec 23 '18 at 13:48
  • 2
    $\begingroup$ Dear Zhi-Wei, the book mentions the author (M. Zhang). Usually such books do not contain the full references to the original papers. $\endgroup$ – Fedor Petrov Dec 23 '18 at 14:42
3
$\begingroup$

Vess's solution is correct (as we could expect from him). After expanding the brackets, we get an alternating sum of the exponents, for a set $I\subset \{1,2,\dots,n\}$ we have a summand $(-1)^{n-|I|} e^{2\pi i (A_Ix+B_I)}$, where $A_I=\sum_{j\in I} \frac1{b_j}$, $B_I=-\sum_{j\in I} \frac{a_j}{b_j}$.

You may finish it by averaging not over large segments of integers and taking the limit, but over $x=0,1,\dots,lcm(b_1,\dots,b_n)-1$.

Essentially the same argument may be read as follows. Denote $N=lcm(b_1,\dots,b_n)$ and consider the polynomial $f(z)=\prod_{j=1}^n (z^{N/b_j}-e^{2\pi i a_j/b_j})$. You are given that any root of $z^N-1$ is a root of $f$, so $f$ is divisible by $z^N-1$. Expand the brackets in $f$ and reduce it modulo $z^N-1$. This is the same as reducing each exponent of $z$ modulo $N$. Since we get 0 after total reduction, $f$ should contain some exponent divisible by $N$ other than the constant term. This is what we need.

$\endgroup$
  • $\begingroup$ Thank you for you answer. Can you explain why if no $ A_I$ with $ I\ne\varnothing$ is an integer, then the right hand side is $ (-1)^n$ ? $\endgroup$ – color Dec 23 '18 at 12:47
  • $\begingroup$ Because if $A_I\notin \mathbb{Z}$, we have $A_I=p/q$ where $p,q$ are coprime and $q>1$ is a divisor of $lcm(b_1,\dots,b_n)$. Then $\sum e^{2\pi i A_I\cdot x}$ when $x$ runs over $q$ consecutive integers equals 0. $\endgroup$ – Fedor Petrov Dec 23 '18 at 13:21
  • $\begingroup$ @Fedor Petrov, please visit the links in my answer. Vess's and your explanations are essential the same as my earlier observations mentioned in the linked talks. $\endgroup$ – Zhi-Wei Sun Dec 23 '18 at 13:58
  • $\begingroup$ @Fedor Petrov, please visit the links in my answer. Vess's and your explanations are essential the same as my earlier observations mentioned in the linked talks. $\endgroup$ – Zhi-Wei Sun Dec 23 '18 at 13:58
  • $\begingroup$ About your solution,$f$ indeed should contain some exponent divisible by N other than the constant term, however what if the exponent can be equal to $\frac{N^k}{b_1b_2...b_k}$, with some $k>1$? $\endgroup$ – color Dec 23 '18 at 13:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.