Suppose that the \(n\)th prime number is given by \(p_n\) and the number of primes that do not exceed \(n\) is \(\pi(n)\). Let two functions \(f\) and \(g\) be asymptotic to each other, denoted by \(f\sim g\), iff \(\lim_{x\rightarrow\infty}{\frac{f(x)}{g(x)}}=1\). The prime number theorem states
\[\pi(x)\sim \frac{x}{\log{x}}.\] This statement happens to be equivalent to \(p_n\sim x\log{x}\). I will show this equivalence, using the argument made in An Introduction to the Theory of Numbers, though with much of the gaps and leaps in reasoning filled in by myself. The first thing to note is that \(p_n\) and \(\pi(n)\) are inverse functions. That is, \(\pi(p_n)=n\) and \(p_{\pi(n)}=n\). Now, we consider the function \[y=\frac{x}{\log{x}}.\] Taking the logarithm of both sides, we obtain, \[\log{y}=\log{x}-\log{\log{x}}.\] Now, we show that \(\log{\log{x}}=o(\log{x})\). By L'Hôpital's rule, \[\lim_{x\rightarrow\infty}{\frac{\log{\log{x}}}{\log{x}}}=\lim_{x\rightarrow\infty}{\frac{1}{\log{x}}}=0,\] as desired. So now, we can divide the logarithm of \(y\) by the logarithm of \(x\) to obtain \[\frac{\log{y}}{\log{x}}=1-\frac{\log{\log{x}}}{\log{x}}.\] In the limit, this approaches 1, so that \(\log{y}\sim \log{x}\). Hence, when we have \[x=y\log{x},\] we have that the LHS is the inverse of \(y\), but \(\log{x}\) is asymptotic to \(\log{y}\), so the inverse of \(y\) is asymptotic to \(y\log{y}\). Now, it suffices to show that for two divergent functions \(f\sim g\), we must also have \(f^{-1}\sim g^{-1}\). Observe that \[f^{-1}(f(x))=x\Rightarrow\lim_{x\rightarrow\infty}{\frac{f^{-1}(f(x))}{x}}=1.\] Likewise, we have \[\lim_{x\rightarrow\infty}{\frac{g^{-1}(g(x))}{x}}=1.\] But since \(f\sim g\), we can replace \(g\) with \(f\) in the limit to obtain \[\lim_{x\rightarrow\infty}{\frac{g^{-1}(f(x))}{x}}=1.\] Dividing our two limits, we obtain \[\lim_{x\rightarrow\infty}{\frac{f^{-1}(f(x))}{g^{-1}(f(x))}}=1,\] and since \(f\) is divergent, we can write this as \[\lim_{f(x)\rightarrow\infty}{\frac{f^{-1}(f(x))}{g^{-1}(f(x))}}=1,\] so \(f^{-1}\sim g^{-1}\), as desired. Hence, since \(\pi(n)\sim y\), the inverse of \(y\) is asymptotic to \(n\log{n}\), and \(p_n\) is the inverse of \(\pi(n)\), we have \[\boxed{p_n\sim n\log{n}}.\]
0 Comments
Continuing on an MIT pset, we have the following equation for fluid flow. Let \(\mathbf{F}(x,y,t)=\rho (x,y,t)\mathbf{v}(x,y,t)\), where \(\rho\) is density and \(\mathbf{v}\) is velocity. Then,
\[\frac{\partial\rho}{\partial t}+\nabla\cdot\mathbf{F}=0.\] This is the so-called equation of continuity. As it turns out, it is simply equivalent to the conservation of mass. We can see this by integrating the equation over some region \(R\). We obtain \[\iint_{R}{\frac{\partial\rho}{\partial t}\textrm{ d}A}=-\iint_{R}{\nabla\cdot\mathbf{F}\textrm{ d}A}.\] But now, using Green's theorem in normal form, the RHS becomes a line integral over \(C\), which is the positively-oriented boundary of \(R\): \[\iint_{R}{\frac{\partial\rho}{\partial t}\textrm{ d}A}=-\oint_{C}{M\textrm{ d}y-N\textrm{ d}x},\] where \(M\) and \(N\) are the \(x\) and \(y\) components of \(\mathbf{F}\), respectively. Observe that the RHS is now the negative of the fluid flux through \(C\). That is, the change in pressure over a region is equal to the negative of the flux through the boundary of that region. Obviously. If mass wants to leave a region, it must pass through the boundary of that region. It cannot simply "vanish". Mass is conserved. In a previous blog post, we talked about the convective derivative, and how it is used in defining incompressible flow. In particular, a flow is incompressible when the convective derivative of the pressure is zero. We can combine this with the equation of continuity to find another necessary and sufficient condition for flow incompressibility. We have \[\begin{split} \frac{D\rho}{Dt}&=\frac{\partial\rho}{\partial t}+\mathbf{v}\cdot\nabla\rho\\ &=0. \end{split}\] But by rearranging the product rule, we have \(\mathbf{v}\cdot\nabla\rho=\nabla\cdot(\rho\mathbf{v})-\rho\nabla\cdot\mathbf{v}\). So our convective derivative becomes \[\frac{\partial\rho}{\partial t}+\nabla\cdot(\rho\mathbf{v})-\rho(\nabla\cdot\mathbf{v})=0.\] The first two terms sum to zero by the equation of continuity, which leaves us with \(\boxed{\nabla\cdot\mathbf{v}=0}\). Flow is incompressible only when the divergence of the velocity is zero. My first Putnam is over and I solved two of the problems. They are probably not the best written solutions. I am usually quite elaborate when I am able to type solutions, but the problem is the Putnam is timed. And written. Here is one of the problems that I solved.
2019 A1: Determine all possible values of the expression \[A^3+B^3+C^3-3ABC\] where \(A\), \(B\), and \(C\) are nonnegative integers. Solution: My first thoughts:
I messed around with a few representations of the expression with \((A+B+C)^3\). But then I asked myself what is the point? What am I trying accomplish? I needed to find the types of numbers that the expression could be. How could I even characterize that? Clearly, they must be integers, and by AM-GM, they must be nonnegative integers. What characteristics were they expecting me to use to describe the range? Prime or composite? Number of factors? Divisibility? Divisibility seemed to be the natural answer, and I prepared myself for some modular arithmetic. But now what? Time to generate numbers I suppose. I won't pain you through all the computations but what was very insightful is the manner in which I generated the triples. I fixed \(A\), and then let \(B\) and \(C\) run through the nonnegative integers less than or equal to \(A\). Once I ran through all unique combinations (permutations don't matter because the expression is symmetric in all three variables), I incremented \(A\) and repeated the process. I noticed that I was sometimes hitting on the same number twice, but it seemed that letting \(B\) and \(C\) be numbers that were either equal to \(A\) or one less than \(A\) always generated a new number. Let's try this out. Suppose that WLOG \(A=B=n\), and \(C=n-1\). Then \[\begin{split} A^3+B^3+C^3-3ABC&=2n^3+(n-1)^3-3n^2(n-1)\\ &=2n^3+n^3-3n^2+3n-1-3n^3+3n^2\\ &=3n-1 \end{split}\] Aha! So we can construct every positive integer congruent to 2 modulo 3. Likewise, we find that the expression yields \(3n-2\) when we set \(A=n\) and \(B=C=n-1\), so we can also construct every positive integer congruent to 1 modulo 3. Now we know that every positive integer that is not a multiple of 3 is in the range. How about multiples of 3? Strangely, I was not able to construct 3 or 6 with the triples that I tried, and it did not seem like higher triples would generate these numbers, as the repeat hits that I was getting occurred relatively quickly after the first triple I found that generated that particular number. I was, however, able to construct 9 and 18 with any permutations of the triples \((0,1,2)\) and \((1,2,3)\), respectively. This strongly suggested that I try out a permutation of \((n,n-1,n-2)\). Doing the algebra, I indeed found that the expression simplified to \(9(n-1)\). So now I know that I can construct any positive multiple of 9. At this point, I conjecture that I cannot construct a multiple of 3 that is not a multiple of 9. Another way to frame this is, if there is a multiple of 3 in the range, then it must also be a multiple of 9. If the expression was a multiple of 3, since obviously \(3ABC\equiv0\pmod{3}\), I required \(A^3+B^3+C^3\equiv0\pmod{3}\). I had also observed (a bit earlier if I remember correctly) that \(n^3\equiv n\pmod{3}\) in all three possible cases. So now, we simply required \(A+B+C\equiv0\pmod{3}\). There are precisely four cases where this occurs. Case 1: \((A,B,C)\equiv (0,0,0)\pmod{3}\) In this case, all three numbers have at least one factor of 3, so their cubes have at least three factors of 3. Furthermore, the product \(3ABC\) must have at least four factors of 3. Hence, we have in this case \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] Case 2: \((A,B,C)\equiv (1,1,1)\pmod{3}\) We can write \(A=3x+1\), \(B=3y+1\), and \(C=3z+1\) for \(x,y,z\in\mathbb{Z}\). Plugging these into the expression, we find that the expansion consists of coefficients that are all divisible by 9. Hence, once again we obtain \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] Case 3: \((A,B,C)\equiv (2,2,2)\pmod{3}\) Similar to the previous case, we bash out the expression, but setting \(A=3x+2\), \(B=3y+2\), and \(C=3z+2\) this time. Once again, the coefficients end up being divisible by 9. Hence in this case, \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] Case 4: \((A,B,C)\equiv \textrm{some permutation of }(0,1,2)\pmod{3}\) In this case, WLOG let the permutation of the ordered triple above be \((0,1,2)\). Then, by our arguments in the first case, both \(A^3\) and \(3ABC\) are divisible by 9. For the remaining terms, we have \[\begin{split} B^3+C^3&=(B+C)(B^2+C^2-BC)\\ &\equiv (1+2)(1+4-2)\pmod{3} \end{split}\] Observe that both factors are congruent to 0 modulo 3, so the sum \(B^3+C^3\) is also divisible by 9. Hence we have in this case \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] So we can see that we can construct 0 (duh), every positive integer that is not a multiple of 3, every positive integer that is a multiple of 9, and that whenever we construct a multiple of 3 it must also be a multiple of 9. So the range is all nonnegative integers except for multiples of 3 which are not multiples of 9. \(\square\) Phew! |
Categories
All
Archives
July 2023
|