number_theory_talk
system:sage


<h1><span style="color: #008000;">Analytic Number Theory with Sage</span></h1>
<p><span style="color: #339966;"><span style="color: #000000;">Analytic number theory begins with estimations on Prime Numbers. <br /></span></span></p>
<p><span style="color: #339966;"><span style="color: #000000;"> The Prime Number Theorem says $\pi(x):= |\{\text{primes} \leq x\}|$ is asymptotic to $\frac{x}{\log(x)}$.</span></span></p>
<p><span style="color: #339966;"><span style="color: #000000;">In sage we </span><span style="background-color: #ffffff; color: #000000;">don't need to write a program for values of $\pi(x)$ as there is already this built in function available!<br /></span></span></p>
<p><span style="color: #339966;"><span style="color: #000000;"><br /></span></span></p>

{{{id=1|
prime_pi?
///
<html><!--notruncate-->

<div class="docstring">
    
  <p><strong>File:</strong> /usr/lib/sagemath/devel/sage/sage/functions/prime_pi.pyx</p>
<p><strong>Type:</strong> &lt;type &#8216;sage.functions.prime_pi.PrimePi&#8217;&gt;</p>
<p><strong>Definition:</strong> prime_pi(x, mem_mult=1)</p>
<p><strong>Docstring:</strong></p>
<blockquote>
<div><p>Return the number of primes <span class="math">\leq x</span>.</p>
<p>EXAMPLES:</p>
<div class="highlight-python"><div class="highlight"><pre class="literal-block"><span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mi">7</span><span class="p">)</span>
<span class="go">4</span>
<span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="go">25</span>
<span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mi">1000</span><span class="p">)</span>
<span class="go">168</span>
<span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mi">100000</span><span class="p">)</span>
<span class="go">9592</span>
<span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mf">0.5</span><span class="p">)</span>
<span class="go">0</span>
<span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="o">-</span><span class="mi">10</span><span class="p">)</span>
<span class="go">0</span>
<span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mi">500509</span><span class="p">)</span>
<span class="go">41581</span>
</pre></div>
</div>
<p>The following test is to verify that ticket #4670 has been essentially
resolved:</p>
<div class="highlight-python"><div class="highlight"><pre class="literal-block"><span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mi">10</span><span class="o">**</span><span class="mi">10</span><span class="p">)</span>
<span class="go">455052511</span>
</pre></div>
</div>
<p>The prime_pi function allows for use of additional memory:</p>
<div class="highlight-python"><div class="highlight"><pre class="literal-block"><span class="gp">sage: </span><span class="n">prime_pi</span><span class="p">(</span><span class="mi">500509</span><span class="p">,</span> <span class="mi">8</span><span class="p">)</span>
<span class="go">41581</span>
</pre></div>
</div>
<p>The prime_pi function also has a special plotting method, so it plots
quickly and perfectly as a step function:</p>
<div class="highlight-python"><div class="highlight"><pre class="literal-block"><span class="gp">sage: </span><span class="n">P</span> <span class="o">=</span> <span class="n">plot</span><span class="p">(</span><span class="n">prime_pi</span><span class="p">,</span> <span class="mi">50</span><span class="p">,</span><span class="mi">100</span><span class="p">)</span>
</pre></div>
</div>
</div></blockquote>


</div>
</html>
}}}

{{{id=4|
prime_pi(12.5)
///
5
}}}

<p>Primes less or equal to 12.5 are 2, 3, 5, 7 and 11. We can make a plot for this function in Sage that can interact.</p>

{{{id=6|
@interact 
def _(n=('Range', 300)):
    show(line([(i, prime_pi(i)) for i in srange(1, n, 0.3)], figsize=4, color='red'))
///
}}}

<p>We may compare the graph of $\pi(x)$ with $\frac{x}{\log(x)}$ by plotting it together.</p>

{{{id=33|
@interact 
def _(n=('Range', 100)):
    x=var('x')
    show(line([(i, prime_pi(i)) for i in srange(1, n, 0.3)], figsize=6, color='red', legend_label='$\pi(x)$') 
    + plot(x/log(x), 2, n, figsize=6, legend_label='$\\frac{x}{\log(x)}$'))
///
}}}

{{{id=43|

///
}}}

{{{id=42|

///
}}}

<p>We see, even though the graphs of $\pi(x)$ and $\frac{x}{\log(x)}$ grow alike, they differ a lot too. This is because $\pi(x)=\frac{x}{\log(x)} + O(\frac{x}{\log^2(x)})$</p>
<p>But there is another function that approximate $\pi(x)$ better. It is the logarithmic integral $Li(x):=\int_1^x{\frac{1}{\log(t)}dt}$. This function is a also built in function in sage.</p>
<p>We will see how the plots of these functions look together.</p>

{{{id=32|
@interact 
def _(n=('Range', 200)):
    x=var('x')
    show(line([(i, prime_pi(i)) for i in srange(1, n, 0.3)], figsize=6, color='red', legend_label='$\pi(x)$') 
    + plot(li(x), 2, n, figsize=6, color='green', legend_label='$Li(x)$') + plot(x/log(x), 2, n, figsize=6,  legend_label='$\\frac{x}{\log(x)}$'))
///
}}}

<p>We see the function $Li(x)$ and $\pi(x)$ are very close to each other. But which one is greater ? Let's do some experiment to find out what is really happening. For this we may plot $Li(x)-\pi(x)$.</p>

{{{id=63|

///
}}}

{{{id=34|
@interact
def _(f=('from', 2), t=('to', 100)):
    x=var('x')
    show(line([(x, li(x)-prime_pi(x)) for x in srange(f, t, 0.2)], figsize=6))
///
}}}

<p>The above graph suggests $\forall x \geq 2$ the difference $Li(x)-\pi(x)\geq 0$. This gives an interesting problem to solve:</p>
<p><span style="color: #3366ff;">Can we find sufficiently large $x$ such that $x&gt;2$ such that $Li(x)-\pi(x)&lt;0$ ? </span></p>
<p><span style="color: #3366ff;">What can we say about<span style="color: #3366ff;"> $\varliminf_{x\to\infty}Li(x)-\pi(x)$ and $\varlimsup_{x\to\infty}Li(x)-\pi(x)$ ?</span><br /></span></p>
<p>Littlewood proved that $\pi(x)&gt;Li(x)$ infinitely often. Skewes proved that the first such number is less than 10^10^10^34. This number is called Skewes' number.</p>
<p>..............................................................................................................................................................................................................</p>
<p>Now we will see, we can go even further in Analytic Number Theory with Sage. Because we can work in complex field and many complex valued functions appearing in Number theory are already implemented in sage. For example the Riemann Zeta Function $\zeta(s):=\sum_{n=1}^{\infty}\frac{1}{n^s}$ for $Re(s)&gt;1$ and defined elsewhere in $\mathbb{C}-\{1\}$ by analytic continuation.</p>

{{{id=45|
CC(zeta(3))
///
1.20205690315959
}}}

{{{id=48|
zeta(1) # zeta has a pole at 1.
///
Infinity
}}}

{{{id=50|
CC(zeta(2+10000*I))
///
0.922315539900211 - 0.258362555325381*I
}}}

<p>$\zeta(s)$ has trivial zeros at even negative even integers which we can see in the graph below.&nbsp;</p>

{{{id=49|
@interact
def _(f=('from', -13), t=('to',-1), fn=('function', 0)):
    x=var('x')
    show(plot(zeta(x), f, t, figsize=6) + plot(fn, f, t, color='red', figsize=6))
///
}}}

<p>In the above plot we may experiment with the order of decay of the Riemann zeta function along positive real axis ($&gt;1$). we may also experiment with the oscillation on negative real axis.</p>
<p>Below is a plot of zeta function $\zeta(\sigma+it)$ when $\sigma\in[-20, 20]$ and $t\in[-20, 20]$. Here brightness characterize the magnitude and hue characterize argument.</p>

{{{id=44|
complex_plot(zeta, (-20, 20), (-40, 40) )
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=36|
@interact
def _(a=('abscissa', 1/2), f=('from', -20), t=('to', 20)):
    z=var('z')
    show(line([(real(zeta(a+I*z)), imag(zeta(a+I*z))) for z in srange(f, t, 0.01)], figsize=6))
///
}}}

<h2><span style="color: #008000;">Multiplication Table&nbsp; Problem</span></h2>
<p><span style="color: #000000;"><span style="color: #000000;">Let&nbsp; </span>$S_{N}:= \{n: n= ab, 1\leq a \leq N, 1\leq b \leq N\}$.</span></p>
<p><span style="color: #000000;">What can we say about $\frac{|S_{N}|}{N^2}$ ? Is it $o(1)$ as $N\rightarrow \infty$ ?</span></p>
<p><span style="color: #000000;">This question was first asked by Erdos and he also gave an answer.<br /></span></p>
<p><span style="color: #000000;">Below is a plot of $\frac{|S(N)|}{N^2}$.<br /></span></p>
<p><span style="color: #000000;"><br /></span></p>

{{{id=39|
def mult_growth(st, end):
    return [(i, len(mult_list(i))) for i in range(st, end+1)]
def mult_list(n):
    L=[i*j for i in range(1, n+1) for j in range(1, n+1)]
    return list(Set(L))
@interact
def mult_growth_graph(st=20, end=400): #f=1/x):
    L=mult_growth(st, end)
    show(line([(A[0], (float(A[1]))/(float(A[0]))^2) for A in L ], ymin=0.25)) #+ plot(f, st, end))
///
}}}

<p>The above graph suggests that $\frac{|S(N)|}{N^2}=o(1)$. Erdos proved that $\frac{|S(N)|}{N^2}=O\left(\frac{1}{(\log N)^\delta\sqrt(\log\log N)}\right)$.</p>
<p>Here $\delta$ is a constant having value $0. 0806\ldots$. Later in $2008$ Kevin Ford proved that $|S(N)|\asymp \frac{N^2}{(\log N)^\delta(\log\log N)^{3/2}} $.</p>
<p>But there is no asymptotic formula known for this problem. This is an interesting Sage project to try ! For example can we find an upper and lower bound to this constant, i.e. find $c_1, c_2$ such that</p>
<p>\[c_1\frac{N^2}{(\log N)^\delta(\log\log N)^{3/2}}\leq |S(N)|\leq c_2\frac{N^2}{(\log N)^\delta(\log\log N)^{3/2}}\]</p>
<p>Another interesting project is to approximate $\delta$ to few more decimal places (without having the expression for delta as in Ford's paper ).</p>
<p>In my research I am interested in what happens if we multiply two arbitrary subsets of $\{1,\ldots,n\}$ with given density. For example define</p>
<p>\[S(a, b, c, d, N):=\{(a+bk)(c+dk): 1\leq a+ bk, c+ dk\leq N\},\]&nbsp; then what can we say about \[\frac{|S(a, b, c, d, N)|}{|S(N)|}\] when a, b, c, d are fixed positive integer and $N\rightarrow\infty$</p>
<p>Below is a graph of $\frac{|S(3, 5, 12, 14, N)|}{|S(N)|}$ for $N\in [1, 2000]$.</p>
<p><img src="arith_3_5_12_14_2000.png" alt="" width="779" height="584" /></p>

{{{id=60|

///
}}}

{{{id=51|
def arith_tab(a, b, c, d, n):
    return [(a + b*i)*(c+ d*j) for i in range(1, (n-a)/b +1) for j in range(1, (n-c)/d+1)]
   
def multiplication_list(n):
    return [i*j for i in range(1,n+1) for j in range(1,n+1)]

def ratio_arith(a, b, c, d, n):
    n_1=len(set(arith_tab(a, b, c, d, n)))
    n_2=len(set(multiplication_list(n)))
    return float(n_1)/float(n_2)
///
}}}

{{{id=53|
@interact
def _(n=('Range', 300), a_1=('a', 2), q_1=('b', 5), a_2=('c', 1), q_2=('d', 3)):
    list=[ratio_arith(a_1, q_1, a_2, q_2, i) for i in range(2, n)]
    show(point([(i+2,list[i]) for i in range(n-2)], figsize=6))
///
}}}

<p>With some modification in Ford's proof, we show that $\frac{|S(a, b, c, d, N)|}{|S(N)|}\asymp_{b, d}1$ as $N\rightarrow\infty$</p>
<p>But what if we take two <span style="color: #800000;">arbitrary</span> subsets $A(N), B(N)\subseteq \{1,\ldots, N\}$ such that $|A(N)|, |B(N)| \geq\delta N$ and consider the ratio $\frac{|A(N)*B(N)|}{|S(N)|}$.</p>
<p>$A(N)*B(N):=\{ab: a \in A(N), b\in B(N)\}$</p>
<p>Below is a plot of $\frac{|A(N)*B(N)|}{|S(N)|}$ for $N\leq 4000 $ , where $A(N), B(N)$ are random subsets $S(N)$ having density $\delta=\frac{1}{70}$.</p>
<p><img src="density1by70-4000.png" alt="" width="779" height="582" /></p>
<p>From the above graph it seems $\frac{|A(N)*B(N)|}{|S(N)|}\asymp_\delta1$ when $\delta$ fixed and $N\rightarrow \infty$. For now I don't have a proof for this claim.</p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p>In the graph below, for a given $\delta$, the point is at $(\delta, f(\delta))$ if: \[f(\delta)=\frac{1}{30}\sum_{i=1}^{30}\frac{|A(N_i)*B(N_i)|}{|S(N_i)|}\]</p>
<p>where $\{N_1,\ldots,N_{30} \}\subseteq [3000, 4000]$ randomly choosen and $A(N_i), B(N_i)$ are random subsets of $\{1,\ldots,N_i\}$ having density $\delta$.</p>
<p>&nbsp;</p>
<p><img src="fnform-100pts-50smp.png" alt="" width="782" height="582" /></p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p>Histogram of elements of multiplicity 2 in $300\times300$ multiplication table.</p>
<p><img src="sage_2mul_300.png" alt="" width="781" height="584" /></p>

<p>Here is an interesting entire function given by $f(n, s)=\sum_{d\mid n}d^s$.</p>

{{{id=62|
def div_sum(n, s):
    L=divisors(n)
    return sum([d^s for d in L])
///
}}}

{{{id=64|
complex_plot(div_sum(13*2, x), (-20, 20), (-20, 20))
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=65|

///
}}}