MATH 130B UCI Number of Prime Divisors of A Random Number Problems i am assign to do second question. write a formal solution as if this was an article for

MATH 130B UCI Number of Prime Divisors of A Random Number Problems i am assign to do second question. write a formal solution as if this was an article for an undergraduate mathematics journal. You willneed to decide how to structure the article and how to guide your readers while remaining appropriatelyformal and concise. Math 130B – Projects
In this writing assignment, you are each assigned one of the problems below, and your task is to
write a formal solution as if this was an article for an undergraduate mathematics journal. You will
need to decide how to structure the article and how to guide your readers while remaining appropriately
formal and concise. If you find it appropriate, you are welcome to discuss additional extensions to the
question asked (such as generalizations or open questions). This would increase your grade. For some of
these problems, there can be many different proofs, and it may be worth presenting alternative proofs
as well. The length of the paper is not fixed; you should try to give justice to the problem being solved.
Nevertheless, in no case can the paper be longer than 10 pages or shorter than 5 pages.
If you cannot figure out the mathematics for these problems yourself within a reasonable time, you
can certainly ask us for help. We will also hold Zoom meetings, one for each project, so that all students
working on the same project can ask questions and exchange ideas. Feel free to work in groups, but the
write-up should be done individually.
1
No monochromatic sumsets
For every subset A := {a1 , . . . , ak } ⊆ N define its sum-set to be
(
)
X
S(A) :=
ai xi | xi ∈ {0, 1} for all 1 ≤ i ≤ k .
i
For example, for A = {1, 3, 4} we have
S(A) = {1, 3, 4, 5, 7, 8},
where for A = {1, 2} we have
S(A) = {1, 2, 3}.
Consider the set of integers [n] := {1, . . . , n}. We call A ⊆ [n] relevant if and only if S(A) ⊆ [n] (for
example, if you take a set that contains both n − 10 and 12, then since (n − 10) + 12 ∈
/ [n], this set is
not relevant). Now, given a function f : [n] → {Red, Blue} (we refer to f as a 2-coloring of [n]), we say
that f is k-valid if for every relevant subset A ⊆ [n] of size k we have that S(A) is not monochromatic;
that is, for every relevant set A ⊆ [n] of size k there exist x 6= y ∈ S(A) with f (x) 6= f (y).
Next we define, for every k ∈ N, the function F (k) as the maximum integer n for which there exists
a k-valid 2-coloring of [n]. In this project we will prove that F (k) has (at least) a double exponential
type behavior. There are multiple ways to approach this problem, one good option is as follows:
(a) Try to understand the problem by considering the case k = 2.
(b) Prove that there exists a constant c (independent of k) such that for every subset A ⊆ [n] of size k
we have |S(A)| ≥ ck 2 .
1
(c) Find a bound on n using a random coloring strategy (that is, what is the largest n for which you can
still prove the existence of a k-valid coloring using a random coloring?), and identify the weakest
point in the proof.
(d) Show that if A is a set of size k with |S(A)| ≤ 2k − 2, then there exists x ∈ N with both x and 2x
in S(A).
(e) For each odd number x ∈ [n], let Gx = {x, 2x, 4x, 8x, . . .} ∩ [n] be the geometric sequence starting
S
at x. Prove that x Gx = [n] and that Gx ∩ Gy = ∅ for all x 6= y.
(f) Suppose that you take any coloring of the odd numbers, and for each odd x you extend the coloring by alternating colors in Gx . Show that no relevant subset A ⊆ [n] with |S(A)| ≤ 2k − 2 is
monochromatic. Moreover, for each relevant set A with |S(A)| = 2k − 1, show that S(A) intersects
at least 2k−1 distinct Gx ’s.
(g) Now, instead of taking an arbitrary coloring, take a random 2-coloring of the odd numbers and
extend it to the even numbers as described in (f). What is the largest n for which you can prove
that the expected number of relevant A’s with a monochromatic S(A) is smaller than 1. Conclude
that, for such an n, a k-valid coloring exists.
The list above is a guide for how to gain understanding of the problem, but the paper must not be
a list; it should be cohesive, with sections that are motivated and flow well.
You could provide alternate proofs for your results, if appropriate. You could also consider extensions
such as adding more colors or considering other sets instead of sum sets.
2
Number of Prime Divisors of a Random Number
For a positive integer n, let ν(n) denote the number of primes dividing n. The goal of this project is to
study the behavior of the parameter ν(n). First, we aim to prove the following theorem.
Theorem 1. Let ω(n) be any function such that ω(n) → ∞ when n goes to infinity. Then the number
of x in [n] such that
p
|ν(x) − log log n| > ω(n) log log n
(1)
is o(n).
In a sense, this theorem says that for large n, most integers in [n] have around log log n prime
divisors.
(a) Choose x randomly from {1, 2, . . . , n} and set M = n1/100 . Let X be the number of primes less
than M dividing x. Show that

X 1
1
E[X] =
+O
.
p
n
p≤M
2
(2)
Using the fact (can you prove it?) that
X1
= log log n + O(1),
(3)
Var[X] = log log n + O(1)
(4)
p≤n
p
conclude that E[X] = log log n + O(1).
(b) Show that
and use Chebyshev’s inequality to deduce that
h
i
p
1
Pr |X − log log n| > t log log n 0. Conclude that the same holds for ν in place of X and that Theorem 1 follows.
Theorem 1 is already a pretty good concentration result, but we will now turn to prove something
even more precise. We’ll prove the following, stronger theorem.
Theorem 2. Let λ be a fixed real number. Then
Z ∞
o
p
1 n
1
2
√ e−t /2 dt.
lim
x : 1 ≤ x ≤ n, ν(x) > log log n + λ log log n =
n→∞ n
2π
λ
You might recognize the integral as the tail of a normal distribution. What this theorem really says
is that ν behaves like a normal random variable with mean and variance log log n.
(c) Fix some function s(n) with s(n) → ∞ and s(n) = o((log log n)1/2 ) and set M = n1/s(n) . Like in
part (a), pick x at random in [n] and let X be the number of prime divisors of x less than M . Now
P
for every prime p, define the independent random variables Yp ∼ Bern(1/p). Set Y = p≤M Yp .
How are X and Y related?
Compute µ = E[Y ] and σ 2 = Var[Y ]. By the central limit theorem Ỹ = (Y − µ)/σ converges
to a standard normal random variable g ∼ N (0, 1) in distribution. One property of the normal
distribution is that this implies convergence of the moments: E[Ỹ k ] → E[g k ] for all positive integers
k.
(d) Let X̃ = (X − µ)/σ. Show that
E[X̃ k ] − E[Ỹ k ] = o(1).
Using the fact that convergence to Gaussian moments implies convergence in distribution to a
normal random variable, conclude that X̃ approaches g in distribution. Deduce Theorem 2.
3
Balls and bins
Suppose that there are n balls and n bins, and each ball is placed into exactly one bin independently
at random.
3
(a) What is the probability that there are no unoccupied bins?
Since the probability to have unoccupied bins is quite high, there must be some bins loaded with
more than one ball. Let M (n) be the number of balls in the most loaded bin.
(b) Show that, assuming that n is sufficiently large, with probability at least (say) 9/10 we have that
M (n) = Θ( logloglogn n ) (note that you need to prove both a lower and an upper bound!).
Now, we show that the bound decreases by a lot if we slightly change the model. We still have n
balls and n bins, but at each time step i, we pick two bins independently at random and then place
ball i into the least loaded bin among these two.
Let M2 (n) denote the size of the most loaded bin at the end of this process. Our main goal is to
show that in this model, with high probability we have that M2 (n) = O(log log n). There are many
ways to prove it, and here we chose an approach which is based on random graphs.
Start with n isolated vertices (that is, there are no edges connecting them) corresponding to the
bins. Now at each time step i, pick two vertices (bins) uniformly at random and add an edge ei between
them. Direct this edge towards the bin that we place the i-th ball into (think of ei as an arrow pointing
to that vertex). Note that two vertices might have many edges between them!
Our goal is to show that at the end of this process (meaning, after we add n random directed edges),
no vertex has more than C log log n many arrows pointing towards it for some C > 0. For technical
reasons, it will be easier to assume that we only throw n/1000 balls (therefore, edges) into bins.
(c) Assuming we can prove this bound for n/1000 balls, show that we can prove a similar bound for
n balls.
(d) Call the graph that this procedure produces G. Show that every connected component of G is of
size O(log n).
(e) Show that there is a large constant K, such that every subset X ⊆ V (G) of size at least K spans
a subgraph with average degree at most 5 (recall that the sum of the degrees in a graph equals
twice the number of edges).
Now, consider the following process, at each time step j, remove all the vertices of degree at most
10 from the graph and delete all eges connected to them. Repeat this process until no such vertices
exist.
(f ) Show that this process ends after O(log log n) time steps, and that each remaining connected
component is of size at most K.
(g) Show that every bin (or vertex) has load at most 10i + K, where i is the last time step the vertex
“survived” before being removed from the graph in the above deleting process.
(h) Deduce the theorem under the assumption that there are n balls and not the assumed n/1000.
4
4
Random graphs
Given a positive integer n and a probability 0 1, can you prove
something like that?)
(c) For which p (as a function p(n) of n), does the random graph G(n, p(n)) have no isolated vertex (i.e.,
a vertex with no edge incident to it)? The type of result you should prove is that if p(n) > (1+) logn n
then the probability that G(n, p(n)) has an isolated vertex tends to 0 as n tends to infinity (say for
fixed > 0), while if p(n)