Educational aspects of mathematics:
Today I read on wiki that Euler, in 1755, managed to compute 20 digits of \pi within one hour by using some Machin-like formula. Seems a bit of a cheating as I'm sure he had known many digits of pi by heart, but anyway.
So today in the calculus class that I'm teaching here at Princeton, I chose a similar quest adopting the difficulty to the class: We computed \sqrt{26} with a relative error of less than 10^{-7}! Also took us an hour almost. Apparently, students seemed way more excited about this way of learning what linearization / differential is
Today I read on wiki that Euler, in 1755, managed to compute 20 digits of \pi within one hour by using some Machin-like formula. Seems a bit of a cheating as I'm sure he had known many digits of pi by heart, but anyway.
So today in the calculus class that I'm teaching here at Princeton, I chose a similar quest adopting the difficulty to the class: We computed \sqrt{26} with a relative error of less than 10^{-7}! Also took us an hour almost. Apparently, students seemed way more excited about this way of learning what linearization / differential is
Today I came across Murmurations of Elliptic Curves (some fascinating plots inside!) and Peter Sarnak's take on this phenomenon, in the format of a 24-page-long handwritten letter!
Does there exist a fixed natural number k such that any finite set of points on the plane has a line through at least two of its points where the number of points on either side of this line differ by at most k?
This question was first raised by Kupitz (and apparently later by many others) and remains open to this day. The best example known is a configuration requiring k to be at least 2. In the opposite direction, Pinchasi proved that k=O(\log\log n) works, where n is the cardinality of the set of points. This improved on the previous bounds of n/3 by Kupitz, O(\sqrt n) Alon, and O(\log n) by Perles.
The proof of Pinchasi doesn't use much about straight lines and, in fact, extends to any generalised configuration, which is collection of points together with a pseudoline arrangement such that each pseudoline contains at least two points and there is a pseudoline through any pair of points. Recall that a pseudoline arrangement is a collection of two-way unbounded simple curves any two of which meet in at most one point.
Very recently, David Conlon and Jeck Lim proved that for generalised configurations the result of Pinchasi is essentially optimal: There exists c>0 such that for large enough n there is a generalised configurations where the number of points on either side of each pseudoline differ by at least c* \log \log n. They also conjecture that similar bound may be true for the original question of Kupitz.
This question was first raised by Kupitz (and apparently later by many others) and remains open to this day. The best example known is a configuration requiring k to be at least 2. In the opposite direction, Pinchasi proved that k=O(\log\log n) works, where n is the cardinality of the set of points. This improved on the previous bounds of n/3 by Kupitz, O(\sqrt n) Alon, and O(\log n) by Perles.
The proof of Pinchasi doesn't use much about straight lines and, in fact, extends to any generalised configuration, which is collection of points together with a pseudoline arrangement such that each pseudoline contains at least two points and there is a pseudoline through any pair of points. Recall that a pseudoline arrangement is a collection of two-way unbounded simple curves any two of which meet in at most one point.
Very recently, David Conlon and Jeck Lim proved that for generalised configurations the result of Pinchasi is essentially optimal: There exists c>0 such that for large enough n there is a generalised configurations where the number of points on either side of each pseudoline differ by at least c* \log \log n. They also conjecture that similar bound may be true for the original question of Kupitz.
Apparently, taking functions f(x)=x+sin(2x)/2 and g(x):=f(x)*e^{sin(x)} one has
f'(x)=2*cos(x)^2 and g'(x)=e^{sin(x)}*cos(x)*[2cos(x)+x+sin(2x)/2]
So naïvely applying L'Hôpital's rule and cancelling cos(x) one would get that
\lim_{x --> \infty} f'(x)/g'(x) = 0 and so \lim_{x --> \infty} f(x)/g(x) = 0,
which is clearly nonsense. This "counterexample" is due to Otto Stolz. Here is a more general construction.
f'(x)=2*cos(x)^2 and g'(x)=e^{sin(x)}*cos(x)*[2cos(x)+x+sin(2x)/2]
So naïvely applying L'Hôpital's rule and cancelling cos(x) one would get that
\lim_{x --> \infty} f'(x)/g'(x) = 0 and so \lim_{x --> \infty} f(x)/g(x) = 0,
which is clearly nonsense. This "counterexample" is due to Otto Stolz. Here is a more general construction.
Here is a story of one particular PhD General Examination at Princeton. I am kinda glad I didn't have to go through it! Never have I ever knew enough of maths to pass this sort of examination.
Mathematically interesting from the story: the question "Given, positive integers N, A, B, does there exist a divisor of N which is in [A, B]" is NP-complete. I haven't managed to google the reduction to the subset sum and the naïve approach seems to require being able to deterministically produce large primes which is hard. So if anyone knows the answer and/or is more proficient in googling, let me know.
Also, apparently Peter Sarnak thinks that factoring is in P. Not sure how wide-spread this belief is.
Mathematically interesting from the story: the question "Given, positive integers N, A, B, does there exist a divisor of N which is in [A, B]" is NP-complete. I haven't managed to google the reduction to the subset sum and the naïve approach seems to require being able to deterministically produce large primes which is hard. So if anyone knows the answer and/or is more proficient in googling, let me know.
Also, apparently Peter Sarnak thinks that factoring is in P. Not sure how wide-spread this belief is.
Marden's theorem states that if complex numbers a, b, c forming a triangle on the complex plane are roots of some cubic polynomial P(x), then roots p, q of its derivate P'(x) are exactly the foci of the unique ellipse inscribed in the triangle and touching its sides at the midpoints of edges.
Here is a short proof which came out of a discussion with Daniel Zhu (though I'd thought everyone knew roughly this proof). Without loss of generality we assume that P is monic.
1)Note that (p-a)(q-a)=P'(a)/3 and (c-a)(b-a)=P'(a) which implies that p and q are isogonally conjugate in the angle BAC. Similarly, for the other two angles of the triangle. This means that P and Q are isogonally conjugate in ABC and hence there is an ellipse E with foci P, Q inscribed in ABC (P, Q are inside the triangle by the Gauss-Lucas theorem).
2)Note that (a+b+c)/3=(p+q)/2 is the unique root of P''(x), so the center of this ellipse is the barycenter of the triangle. Hence, concidering an affine transformation which maps ellipse E to a circle, we obtain a new triangle in which the incribed circle has center coinsiding with the barycenter, so this triangle will be an equilateral triangle. Inscribed circle of the equilateral triangle touches its sides at midpoints so the same is true for the original ellipse.
Here is a short proof which came out of a discussion with Daniel Zhu (though I'd thought everyone knew roughly this proof). Without loss of generality we assume that P is monic.
1)Note that (p-a)(q-a)=P'(a)/3 and (c-a)(b-a)=P'(a) which implies that p and q are isogonally conjugate in the angle BAC. Similarly, for the other two angles of the triangle. This means that P and Q are isogonally conjugate in ABC and hence there is an ellipse E with foci P, Q inscribed in ABC (P, Q are inside the triangle by the Gauss-Lucas theorem).
2)Note that (a+b+c)/3=(p+q)/2 is the unique root of P''(x), so the center of this ellipse is the barycenter of the triangle. Hence, concidering an affine transformation which maps ellipse E to a circle, we obtain a new triangle in which the incribed circle has center coinsiding with the barycenter, so this triangle will be an equilateral triangle. Inscribed circle of the equilateral triangle touches its sides at midpoints so the same is true for the original ellipse.
Wikipedia
Marden's theorem
Geometric relationship between the zeros of a cubic polynomial and of its derivative
Apparently, Terrence Tao believes (see his lecture on youtube and also this paper of his) that Navier-Stokes equations can blow up in finite time. Do many people believe that?
His argument is roughly: Water is "Turing complete" so it should be possible to somehow push all the energy into smaller and smaller part of space making the solution blow up (as the equation is supercritical, whatever that means).
Anyone more knowledgeable about these things is very welcome to explain to me how solid this heuristics is!
His argument is roughly: Water is "Turing complete" so it should be possible to somehow push all the energy into smaller and smaller part of space making the solution blow up (as the equation is supercritical, whatever that means).
Anyone more knowledgeable about these things is very welcome to explain to me how solid this heuristics is!
My coauthor Zhi-Wei Sun is known for publishing a plethora of conjectures every few years, many of them are mathematically meaningless (i.e. not shedding any light on anything, sometimes clearly way too hard for the current methods, etc).
Most of his conjectures involve prime numbers (typical example: any integer n>1 can be written as a+b such that a+2^b prime), infinite sums involving binomial coefficients, polynomials and exponents, or sums modulo a power of a prime number. There is some not yet well understood correspondence between infinite sums having explicit values and their p-adic analogues where trancated sum up to p-1 can be evaluated modulo some power of p.
Here is an example of a paper of Sun with ~100 new conjectures of the second and third kind. Some of the conjectures of Sun are proved by very elementary methods. Some of them are proved by literally asking Mathematica "Prove this identity" and waiting for an hour, some are proved using non-trivial ideas. But usually all the methods are rather ad hoc and don't provide much insight.
I recently came across a paper by Kam Cheong Au which explains what methods exist for proving these sort of conjectures and then explains a new connection between some of them. I found most of the paper hard to read but the introduction is very nice. Au also proves dozens of Conjectures of Sun along the way
Most of his conjectures involve prime numbers (typical example: any integer n>1 can be written as a+b such that a+2^b prime), infinite sums involving binomial coefficients, polynomials and exponents, or sums modulo a power of a prime number. There is some not yet well understood correspondence between infinite sums having explicit values and their p-adic analogues where trancated sum up to p-1 can be evaluated modulo some power of p.
Here is an example of a paper of Sun with ~100 new conjectures of the second and third kind. Some of the conjectures of Sun are proved by very elementary methods. Some of them are proved by literally asking Mathematica "Prove this identity" and waiting for an hour, some are proved using non-trivial ideas. But usually all the methods are rather ad hoc and don't provide much insight.
I recently came across a paper by Kam Cheong Au which explains what methods exist for proving these sort of conjectures and then explains a new connection between some of them. I found most of the paper hard to read but the introduction is very nice. Au also proves dozens of Conjectures of Sun along the way
Back to more reasonable mathematics.
One of the beautiful and fascinating things about planar percolation is the existence of rational critical exponents, i.e. powers in the polynomial decay of quantities at criticality. For instance, consider this statement:
Theorem: On the hexagonal grid, color each cell black or white with probability 1/2. Then the probability that the origin is connected to a cell at distance N from it decays as N^{-5/48+o(1)}.
This result was first proved here as a consequence of conformal invariance (e.g. Cardy's formula) proved by Smirnov (here is a modern exposition of his proof). Some other exponents, for example, the full-plane two-arm exponent (corresponding to the probability of having both a white and a black path of cells to distance N), are easier to compute, see this paper. All computations of arm exponents followed the same strategy: use Cardy's formula to show SLE_6 convergence of interfaces and then compute the corresponding "continuous" version of exponents for the SLE_6 process. At this point it usually doesn't matter if \kappa=6 or not.
The question then boils down to some PDE computation which an observable of SLE_\kappa satisfies. One prominent exponent which was not computed in this way is the so-called backbone exponent: corresponding to the probability of having two disjoint arms to distance N. The problem isn't that the stochastic calculus is harder for this case but rather that the PDE question couldn't be answered. Here is the PDE question (see page 16 here):
Let T be the triangle given by {x>0, y>0, x+y<2*\pi}. Consider an operator
D:=3(\partial_x^2-2\partial_x\partial_y+\partial_y^2)+\cot{(x/2)}\partial_x-\cot{(y/2)}\partial_y
Then the backbone exponent is the unique \lambda > 0 such that -\lambda is the eigenvalue corresponding to a non-negative function G(x, y) on T with boundary conditions
G(x, 2*\pi-x) = 0, G(0, y) = 1, \partial_y G(x, 0) = 0.
==================
The authors, smart as they are, couldn't solve this PDE explicitly and so no formula for the backbone exponent was known. It had been assumed to be 6/17 (though I struggle to find any explicit conjectures about it from mathematicians, only from some physicists from 80's and 90's) but later simulations showed this is likely not the case. Very recently the following result was proved using Liouville quantum gravity (LQG) techniques:
Theorem: Backbone exponent is equal to (x^2-1)/12, where x \in (2, 3) is the unique root of
\sqrt{3}*x/4+\sin(2\pi x / 3) = 0.
Given how complicated the proof is, a natural question to ask is: Could this implicitly given value suggest something about the solution of the PDE, leading to a much simpler derivation of the exponent?
One of the beautiful and fascinating things about planar percolation is the existence of rational critical exponents, i.e. powers in the polynomial decay of quantities at criticality. For instance, consider this statement:
Theorem: On the hexagonal grid, color each cell black or white with probability 1/2. Then the probability that the origin is connected to a cell at distance N from it decays as N^{-5/48+o(1)}.
This result was first proved here as a consequence of conformal invariance (e.g. Cardy's formula) proved by Smirnov (here is a modern exposition of his proof). Some other exponents, for example, the full-plane two-arm exponent (corresponding to the probability of having both a white and a black path of cells to distance N), are easier to compute, see this paper. All computations of arm exponents followed the same strategy: use Cardy's formula to show SLE_6 convergence of interfaces and then compute the corresponding "continuous" version of exponents for the SLE_6 process. At this point it usually doesn't matter if \kappa=6 or not.
The question then boils down to some PDE computation which an observable of SLE_\kappa satisfies. One prominent exponent which was not computed in this way is the so-called backbone exponent: corresponding to the probability of having two disjoint arms to distance N. The problem isn't that the stochastic calculus is harder for this case but rather that the PDE question couldn't be answered. Here is the PDE question (see page 16 here):
Let T be the triangle given by {x>0, y>0, x+y<2*\pi}. Consider an operator
D:=3(\partial_x^2-2\partial_x\partial_y+\partial_y^2)+\cot{(x/2)}\partial_x-\cot{(y/2)}\partial_y
Then the backbone exponent is the unique \lambda > 0 such that -\lambda is the eigenvalue corresponding to a non-negative function G(x, y) on T with boundary conditions
G(x, 2*\pi-x) = 0, G(0, y) = 1, \partial_y G(x, 0) = 0.
==================
The authors, smart as they are, couldn't solve this PDE explicitly and so no formula for the backbone exponent was known. It had been assumed to be 6/17 (though I struggle to find any explicit conjectures about it from mathematicians, only from some physicists from 80's and 90's) but later simulations showed this is likely not the case. Very recently the following result was proved using Liouville quantum gravity (LQG) techniques:
Theorem: Backbone exponent is equal to (x^2-1)/12, where x \in (2, 3) is the unique root of
\sqrt{3}*x/4+\sin(2\pi x / 3) = 0.
Given how complicated the proof is, a natural question to ask is: Could this implicitly given value suggest something about the solution of the PDE, leading to a much simpler derivation of the exponent?
Some news from the world of additive combinatorics: polynomial Freiman–Ruzsa conjecture in \F_2^n was recently proved by Timothy Gowers, Ben Green, Freddie Manners, and Terrence Tao. Moreover, the constants are very explicit; they prove that
If a set A\subset \F_2^n has doubling constant at most K (i.e. |A+A| <= K|A|) then A can be covered by at most 2*K^12 cosets of some subgroup H\subset \F_2^n of size at most |A|.
If a set A\subset \F_2^n has doubling constant at most K (i.e. |A+A| <= K|A|) then A can be covered by at most 2*K^12 cosets of some subgroup H\subset \F_2^n of size at most |A|.
See also a paper A Counterexample to a Strong Variant of the Polynomial Freiman-Ruzsa Conjecture in Euclidean Space for a discussion of the analogous conjecture in \R^n.
Given an n-dimensional cube, any k-dimensional central section which is close to being a sphere (I.e sandwiched between a sphere and its dilate by a factor of 1.1 say) must have k<5*log(n)
Proof sketch: Let T: L^2(\R^k) --> L^\infty (\R^n) be the embedding together with a dilation mapping the boundary of the section to almost the unit sphere of \R^k. Then |x|_{L^2(\R^k)} and |Tx|_{L^\infty(\R^n)} are within 1.1 factor from each other for any vector x in the section. Consider T*, a mapping from the dual spaces, i.e. T*: L^1 (\R^n) --> L^2(\R^k). Then e_j\in L^1 (\R^n) is mapped to some vector y_j\in L^2(\R^k) which is almost of norm 1. We claim that any point y in the unit sphere of L^2(\R^k) is close to one of \pm y_j which ensures that n (half of the number of points \pm y_j) is exponentially large in terms of k.
Indeed, any point x on the boundary of the section has one coordinate (in \R^n) equal to \pm 1, which means that |<x, e_j>|=1. Since T is almost an isometry, Tx has large L^2 scalar product with \pm y_j, which implies that Tx is close to \pm y_j. Since Tx can approximate, within a factor of 1.1, any point on the unit sphere of L^2(\R^k), this completes the proof.
=========
This shows that cubes are asymptotically the worst for Dvoretzky's theorem: Any centrally symmetric convex body in \R^n has a section of dimention at least C(\eps)*log(n) which is 1+\eps close to a sphere (This quantitative version was only later shown by Milman, who also showed that a random section works).
In some sense a cube is a fundamental counterexmaple: If you're OK with the section being close to either a sphere or a cube (i.e. to an L^2 or an L^\infty unit sphere) then N.Alon and Milman show that a much large dimensional section (with dimension k=e^{C(\eps)*\sqrt{\log{n}}}) is possible.
Proof sketch: Let T: L^2(\R^k) --> L^\infty (\R^n) be the embedding together with a dilation mapping the boundary of the section to almost the unit sphere of \R^k. Then |x|_{L^2(\R^k)} and |Tx|_{L^\infty(\R^n)} are within 1.1 factor from each other for any vector x in the section. Consider T*, a mapping from the dual spaces, i.e. T*: L^1 (\R^n) --> L^2(\R^k). Then e_j\in L^1 (\R^n) is mapped to some vector y_j\in L^2(\R^k) which is almost of norm 1. We claim that any point y in the unit sphere of L^2(\R^k) is close to one of \pm y_j which ensures that n (half of the number of points \pm y_j) is exponentially large in terms of k.
Indeed, any point x on the boundary of the section has one coordinate (in \R^n) equal to \pm 1, which means that |<x, e_j>|=1. Since T is almost an isometry, Tx has large L^2 scalar product with \pm y_j, which implies that Tx is close to \pm y_j. Since Tx can approximate, within a factor of 1.1, any point on the unit sphere of L^2(\R^k), this completes the proof.
=========
This shows that cubes are asymptotically the worst for Dvoretzky's theorem: Any centrally symmetric convex body in \R^n has a section of dimention at least C(\eps)*log(n) which is 1+\eps close to a sphere (This quantitative version was only later shown by Milman, who also showed that a random section works).
In some sense a cube is a fundamental counterexmaple: If you're OK with the section being close to either a sphere or a cube (i.e. to an L^2 or an L^\infty unit sphere) then N.Alon and Milman show that a much large dimensional section (with dimension k=e^{C(\eps)*\sqrt{\log{n}}}) is possible.
Let {x} denote the fractional part of x. Then for any positive real numbers x_1,\dots, x_n one has
\sum_i\sum_j {x_i/x_j} < 9n^2/14 and the constant 9/14 is asymptotically sharp.
The inequality is taken from here, an elementary proof is given by Fedya, and a different approach which leads to a weaker bound is outlined by another Fedya.
\sum_i\sum_j {x_i/x_j} < 9n^2/14 and the constant 9/14 is asymptotically sharp.
The inequality is taken from here, an elementary proof is given by Fedya, and a different approach which leads to a weaker bound is outlined by another Fedya.
Math from Krach
Let {x} denote the fractional part of x. Then for any positive real numbers x_1,\dots, x_n one has \sum_i\sum_j {x_i/x_j} < 9n^2/14 and the constant 9/14 is asymptotically sharp. The inequality is taken from here, an elementary proof is given by Fedya, and…
Here is a question related to the approach with Bochner’s theorem (see Fedya’s comment): Is it possible to find a positive majorant g(t)>=({e^t}+{e^(-t)})/2 such that it’s a Fourier transform of a signed measure \mu with \mu_+(\R) exactly equal to 9/14?
A conference is happening in Geneva right now with the usual crowd (+Michael Aizenman). Listening to a talk by Gady Kozma right now. He formulates the following very general conjecture:
Given a finite graph G and a collection of probabilities p_e\in (0, 1) indexed by edges of G, for the (edge) Bernoulli percolation with these probabilities, for any two vertices v, b and a set of vertices A\subset V(G) the following inequality for connection probabilities holds:
P(v <---> b) \geq P(v <---> A)*min_{a\in A} P(a<-->b).
The main theorem of his talk is then
Theorem: Conjecture above implies that \theta(p_c)=0 on \Z^d for any d>=2, i.e. there is no infinite cluster at criticality for the Bernoulli percolation on \Z^d.
Note that this is known for d=2 (via RSW theory) and d>=10 (via lace expansion) and the specific case d=3 remains one of the most prominent open problems in probability.
Given a finite graph G and a collection of probabilities p_e\in (0, 1) indexed by edges of G, for the (edge) Bernoulli percolation with these probabilities, for any two vertices v, b and a set of vertices A\subset V(G) the following inequality for connection probabilities holds:
P(v <---> b) \geq P(v <---> A)*min_{a\in A} P(a<-->b).
The main theorem of his talk is then
Theorem: Conjecture above implies that \theta(p_c)=0 on \Z^d for any d>=2, i.e. there is no infinite cluster at criticality for the Bernoulli percolation on \Z^d.
Note that this is known for d=2 (via RSW theory) and d>=10 (via lace expansion) and the specific case d=3 remains one of the most prominent open problems in probability.
In fact, the following weaker conjecture suffices for the \theta(p_c) result:
For any \eps>0 there exists \delta>0 such that if P(v<--->A)>1-\delta and P(a<--->b)>1-\delta for each a\in A, then P(v<--->b)>1-\eps.
For any \eps>0 there exists \delta>0 such that if P(v<--->A)>1-\delta and P(a<--->b)>1-\delta for each a\in A, then P(v<--->b)>1-\eps.
A Phase Transition for Repeated Averages
Take a vector (x_1,...,x_n) of real numbers (with n large) and at each step take two uniformly chosen indices i, j and replace both x_i and x_j with (x_i+x_j)/2. How fast does the process converge to the vector with all coordinates (x_1+...+x_n)/n in L^1?
It sort of depends on the vector, so let's think about the worst case (1, 0, ..., 0). Turns out the answer is n\log_2{n}/2 with a threshold window of order n\sqrt{\log{n}}, which is rather large
Take a vector (x_1,...,x_n) of real numbers (with n large) and at each step take two uniformly chosen indices i, j and replace both x_i and x_j with (x_i+x_j)/2. How fast does the process converge to the vector with all coordinates (x_1+...+x_n)/n in L^1?
It sort of depends on the vector, so let's think about the worst case (1, 0, ..., 0). Turns out the answer is n\log_2{n}/2 with a threshold window of order n\sqrt{\log{n}}, which is rather large
I was creating an Olympiad maths problem recently, it was “something something if both q and 2q^2+7 are prime” and was completely sure that q=5 works…
Some people never learn from other people’s mistakes, I guess!
Some people never learn from other people’s mistakes, I guess!
Asymptotic spectra: Theory, applications and extensions a survey by Avi Wigderson and Jeroen Zuiddam
I learned about it from an abstract of a talk which is to be given soon at Princeton by Daniel Zhu.
Here is the abstract:
What is the computational complexity of matrix multiplication? What is the Shannon capacity of the 7-cycle? What is the size of the largest set in F_p^n containing no line? It turns out that these questions all are the same "type" of question, and can be unified in a theory of amortization developed by Strassen in the late 1980s. We introduce the basic concepts of this theory, following the recent survey of Wigderson and Zuiddam. Surprisingly, the central construction is quite reminiscent of the definition of an affine scheme.
What does all of this have to do with affine schemes you may ask. The answer is: Let's find out!
I learned about it from an abstract of a talk which is to be given soon at Princeton by Daniel Zhu.
Here is the abstract:
What is the computational complexity of matrix multiplication? What is the Shannon capacity of the 7-cycle? What is the size of the largest set in F_p^n containing no line? It turns out that these questions all are the same "type" of question, and can be unified in a theory of amortization developed by Strassen in the late 1980s. We introduce the basic concepts of this theory, following the recent survey of Wigderson and Zuiddam. Surprisingly, the central construction is quite reminiscent of the definition of an affine scheme.
What does all of this have to do with affine schemes you may ask. The answer is: Let's find out!