Question with the Chinese Remainder Theorem

Watch
_gcx
Badges: 21
Rep:
?
#1
Report Thread starter 1 week ago
#1
Let S \subseteq \mathbb N and let S_p be its image under the map n \mapsto n \mod p for each prime p. Suppose that \# S_p \le p/2 for each p.

Let S[N] = S \cap \{1, 2, \ldots, N\}.

I want to show that \frac {\#S[N]} N \to 0. The hint given is to apply the Chinese Remainder Theorem to the first k primes then take k \to \infty.

I've managed to get that \frac {\#S[m_k]} {m_k} \to 0 where m_k is the product of the first k primes using CRT but not sure about anything more. Bounding \frac {\#S[N]} {N} seemed like the way to go but doesn't seem easy.
Last edited by _gcx; 1 week ago
0
reply
DFranklin
Badges: 18
Rep:
?
#2
Report 1 week ago
#2
It seems that it wouldn't be significantly harder to show \dfrac{#S[j+m_k]-#S[j]}{m_k}\to 0 for any integer j (basically "shifting" the window you're intersecting with S).

That should then be enough to "bridge" intermediate values between m_k and m_{k+1} I think. (You can do jumps of m_k until m_{k+1} directly, and values in-between can't be different enough to break convergence to 0).

May be something more elegant, but I think that works.
0
reply
_gcx
Badges: 21
Rep:
?
#3
Report Thread starter 1 week ago
#3
(Original post by DFranklin)
It seems that it wouldn't be significantly harder to show \dfrac{#S[j+m_k]-#S[j]}{m_k}\to 0 for any integer j (basically "shifting" the window you're intersecting with S).

That should then be enough to "bridge" intermediate values between m_k and m_{k+1} I think. (You can do jumps of m_k until m_{k+1} directly, and values in-between can't be different enough to break convergence to 0).

May be something more elegant, but I think that works.
Cheers, it seems this end of the question is oddly inelegant compared to the previous part.

Is the general idea that #S[N]/N = #S[j + m_k]/(j + m_k) for some k, j, then the RHS vanishes as k -> infinity?
0
reply
DFranklin
Badges: 18
Rep:
?
#4
Report 1 week ago
#4
(Original post by _gcx)
Cheers, it seems this end of the question is oddly inelegant compared to the previous part.

Is the general idea that #S[N]/N = #S[j + m_k]/(j + m_k) for some k, j, then the RHS vanishes as k -> infinity?
So how I'm thinking about it is that we know that for any block [j,j+m_k) we'll have at most m_k / 2^k (I think will be the bound you have but the exact details don't matter) members of S. In particular, we can take blocks in steps of m_k to show #S[N] <=N/2^k when N is a multiple of m_k.

Now what if N>m_k *isn't* a multiple of m_k. Then we have a "partial block" of size N mod m_k at the end. But that block can't contribute more than a full block,so adds at most m_k/2^k to the total. And since N >m_k the contribution of the partial block divided by N must tend to 0 and can't mess things up.
1
reply
_gcx
Badges: 21
Rep:
?
#5
Report Thread starter 1 week ago
#5
(Original post by DFranklin)
So how I'm thinking about it is that we know that for any block [j,j+m_k) we'll have at most m_k / 2^k (I think will be the bound you have but the exact details don't matter) members of S. In particular, we can take blocks in steps of m_k to show #S[N] <=N/2^k when N is a multiple of m_k.

Now what if N>m_k *isn't* a multiple of m_k. Then we have a "partial block" of size N mod m_k at the end. But that block can't contribute more than a full block,so adds at most m_k/2^k to the total. And since N >m_k the contribution of the partial block divided by N must tend to 0 and can't mess things up.
Yup this is exactly the bound I got, I'll have a go with this cheers.

Edit: This makes a lot of sense, thanks a lot, this question was really irritating me.
Last edited by _gcx; 1 week ago
0
reply
DFranklin
Badges: 18
Rep:
?
#6
Report 1 week ago
#6
Maybe slightly nicer is to prove that
#S(jm_k) <= j#S(m_k)
and observe #S(N) <= #S(jm_k) whenever j >= N/m_k to deal with the case where N isn't a multiple of m_k.

It's essentially the same argument but I think it's more elegant (or at least less *inelegant*!)
Last edited by DFranklin; 1 week ago
0
reply
_gcx
Badges: 21
Rep:
?
#7
Report Thread starter 1 week ago
#7
(Original post by DFranklin)
Maybe slightly nicer is to prove that
#S(jm_k) <= j#S(m_k)
and observe #S(N) <= #S(jm_k) whenever j >= N/m_k to deal with the case where N isn't a multiple of m_k.

It's essentially the same argument but I think it's more elegant (or at least less *inelegant*!)
Seems to all check out, thanks. There was a similar idea on a previous sheet about splitting intervals into blocks so I really should've spotted the trick!

Don't think it's strictly necessary to go casewise, the fact that we can split up the interval into at most a + 1 (if we write N = am_k + b) blocks of size at most m_k/2^k seems to give a strict enough bound.
Last edited by _gcx; 1 week ago
1
reply
DFranklin
Badges: 18
Rep:
?
#8
Report 1 week ago
#8
(Original post by _gcx)
Seems to all check out, thanks. There was a similar idea on a previous sheet about splitting intervals into blocks so I really should've spotted the trick!

Don't think it's strictly necessary to go casewise, the fact that we can split up the interval into at most a + 1 (if we write N = am_k + b) intervals of size at most m_k/2^k seems to give a strict enough bound.
Yes that works too.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Which of these would you use to help with making uni decisions?

Webinars (25)
13.51%
Virtual campus tours/open days (42)
22.7%
Live streaming events (17)
9.19%
Online AMAs/guest lectures (18)
9.73%
A uni comparison tool (41)
22.16%
An in-person event when available (42)
22.7%

Watched Threads

View All