The polymath blog

August 9, 2013

Polymath7 research thread 5: the hot spots conjecture

Filed under: hot spots,research — Terence Tao @ 7:22 pm
Tags:

This post is the new research thread for the Polymath7 project to solve the hot spots conjecture for acute-angled triangles, superseding the previous thread; this project had experienced a period of low activity for many months, but has recently picked up again, due both to renewed discussion of the numerical approach to the problem, and also some theoretical advances due to Miyamoto and Siudeja.

On the numerical side, we have decided to focus first on the problem of obtaining validated upper and lower bounds for the second Neumann eigenvalue {\mu_2} of a triangle {\Omega=ABC}. Good upper bounds are relatively easy to obtain, simply by computing the Rayleigh quotient of numerically obtained approximate eigenfunctions, but lower bounds are trickier. This paper of Liu and Oshii has some promising approaches.

After we get good bounds on the eigenvalue, the next step is to get good control on the eigenfunction; some approaches are summarised in this note of Lior Silberman, mainly based on gluing together exact solutions to the eigenfunction equation in various sectors or disks. Some recent papers of Kwasnicki-Kulczycki, Melenk-Babuska, and Driscoll employ similar methods and may be worth studying further. However, in view of the theoretical advances, the precise control on the eigenfunction that we need may be different from what we had previously been contemplating.

These two papers of Miyamoto introduced a promising new method to theoretically control the behaviour of the second Neumann eigenfunction {u_2}, by taking linear combinations of that eigenfunction with other, more explicit, solutions to the eigenfunction equation {\Delta u = - \mu_2 u}, restricting that combination to nodal domains, and then computing the Dirichlet energy on each domain. Among other things, these methods can be used to exclude critical points occurring anywhere in the interior or on the edges of the triangle except for those points that are close to one of the vertices; and in this recent preprint of Siudeja, two further partial results on the hot spots conjecture are obtained by a variant of the method:

  • The hot spots conjecture is established unconditionally for any acute-angled triangle which has one angle less than or equal to {\pi/6} (actually a slightly larger region than this is obtained). In particular, the case of very narrow triangles have been resolved (the dark green region in the area below).
  • The hot spots conjecture is also established for any acute-angled triangle with the property that the second eigenfunction {u_2} has no critical points on two of the three edges (excluding vertices).

So if we can develop more techniques to rule out critical points occuring on edges (i.e. to keep eigenfunctions monotone on the edges on which they change sign), we may be able to establish the hot spots conjecture for a further range of triangles. In particular, some hybrid of the Miyamoto method and the numerical techniques we are beginning to discuss may be a promising approach to fully resolve the conjecture. (For instance, the Miyamoto method relies on upper bounds on {\mu_2}, and these can be obtained numerically.)

The arguments of Miyamoto also allow one to rule out critical points occuring for most of the interior points of a given triangle; it is only the points that are very close to one of the three vertices which we cannot yet rule out by Miyamoto’s methods. (But perhaps they can be ruled out by the numerical methods we are also developing, thus giving a hybrid solution to the conjecture.)

Below the fold I’ll describe some of the theoretical tools used in the above arguments.

(more…)

September 10, 2012

Polymath7 research threads 4: the Hot Spots Conjecture

Filed under: hot spots,research — Terence Tao @ 7:28 pm

It’s time for another rollover of the  Polymath7 “Hot Spots” conjecture, as the previous research thread has again become full.

Activity has now focused on a numerical strategy to solve the hot spots conjecture for all acute angle triangles ABC.  In broad terms, the strategy (also outlined in this document) is as follows.   (I’ll focus here on the problem of estimating the eigenfunction; one also needs to simultaneously obtain control on the eigenvalue, but this seems to be to be a somewhat more tractable problem.)

  1. First, observe that as the conjecture is scale invariant, the only relevant parameters for the triangle ABC are the angles \alpha,\beta,\gamma, which of course lie between 0 and \pi/2 and add up to \pi.  We can also order \alpha \leq \beta \leq \gamma, giving a parameter space which is a triangle between the values (\alpha,\beta,\gamma) = (0,\pi/2,\pi/2), (\pi/4,\pi/4,\pi/2), (\pi/3,\pi/3,\pi/3).
  2. The triangles that are too close to the degenerate isosceles triangle {}(0,\pi/2,\pi/2) or the equilateral triangle {}(\pi/3,\pi/3,\pi/3) need to be handled by analytic arguments.  (Preliminary versions of these arguments can be found here and Section 6 of these notes  respectively, but the constants need to be made explicit (and as strong as possible)).
  3. For the remaining parameter space, we will use a sufficiently fine discrete mesh of angles (\alpha,\beta,\gamma); the optimal spacing of this mesh is yet to be determined.
  4. For each triplet of angles in this mesh,  we partition the triangle ABC (possibly after rescaling it to a reference triangle \hat \Omega, such as the unit right-angled triangle) into smaller subtriangles, and approximate the second eigenfunction w (or the rescaled triangle \hat w) by the eigenfunction w_h (or \hat w_h) for a finite element restriction of the eigenvalue problem, in which the function is continuous and piecewise polynomial of low degree (probably linear or quadratic) in each subtriangle; see Section 2.2 of these notes.    With respect to a suitable basis, w_h can be represented by a finite vector u_h.
  5. Using numerical linear algebra methods (such as Lanczos iteration) with interval arithmetic, obtain an approximation \tilde u to u_h, with rigorous bounds on the error between the two.  This gives an approximation to w_h or \hat w_h with rigorous error bounds (initially of L^2 type, but presumably upgradable).
  6. After (somehow) obtaining a rigorous error bound between w and w_h (or \hat w and \hat w_h), conclude that w stays far from its extremum when one is sufficiently far away from the vertices A,B,C of the triangle.
  7. Using L^\infty stability theory of eigenfunctions (see Section 5 of these notes), conclude that w stays far from its extremum even when (\alpha,\beta,\gamma) is not at a mesh point.  Thus, the hot spots conjecture is not violated away from the vertices.  (This argument should also handle the vertex that is neither the maximum nor minimum value for the eigenfunction, leaving only the neighbourhoods of the two extremising vertices to deal with.)
  8. Finally, use an analytic argument (perhaps based on these calculations) to show that the hot spots conjecture is also not violated near an extremising vertex.

This all looks like it should work in principle, but it is a substantial amount of effort; there is probably still some scope to try to simplify the scheme before we really push for implementing it.

July 12, 2012

Minipolymath4 project: IMO 2012 Q3

Filed under: research — Terence Tao @ 10:00 pm
Tags:

This post marks the official opening of the mini-polymath4 project to solve a problem from the 2012 IMO.  This time, I have selected Q3, which has an interesting game-theoretic flavour to it.

Problem 3.   The liar’s guessing game is a game played between two players A and B.  The rules of the game depend on two positive integers k and n which are known to both players.

At the start of the game, A chooses two integers x and N with 1 \leq x \leq N.  Player A keeps x secret, and truthfully tells N to player B.  Player B now tries to obtain information about x by asking player A questions as follows.  Each question consists of B specifying an arbitrary set S of positive integers (possibly one specified in a previous question), and asking A whether x belongs to S.  Player B may ask as many such questions as he wishes.  After each question, player A must immediately answer it with yes or no, but is allowed to lie as many times as she wishes; the only restriction is that, among any k+1 consecutive answers, at least one answer must be truthful.

After B has asked as many questions as he wants, he must specify a set X of at most n positive integers.  If x belongs to X, then B wins; otherwise, he loses.  Prove that:

  1. If n \geq 2^k, then B can guarantee a win.
  2. For all sufficiently large k, there exists an integer n \geq 1.99^k such that B cannot guarantee a win.
The comments to this post shall serve as the research thread for the project, in which participants are encouraged to post their thoughts and comments on the problem, even if (or especially if) they are only partially conclusive.  Participants are also encouraged to visit the discussion thread for this project, and also to visit and work on the wiki page to organise the progress made so far.
This project will follow the general polymath rules.  In particular:
  1. All are welcome. Everyone (regardless of mathematical level) is welcome to participate.  Even very simple or “obvious” comments, or comments that help clarify a previous observation, can be valuable.
  2. No spoilers! It is inevitable that solutions to this problem will become available on the internet very shortly.  If you are intending to participate in this project, I ask that you refrain from looking up these solutions, and that those of you have already seen a solution to the problem refrain from giving out spoilers, until at least one solution has already been obtained organically from the project.
  3. Not a race. This is not intended to be a race between individuals; the purpose of the polymath experiment is to solve problems collaboratively rather than individually, by proceeding via a multitude of small observations and steps shared between all participants.   If you find yourself tempted to work out the entire problem by yourself in isolation, I would request that you refrain from revealing any solutions you obtain in this manner until after the main project has reached at least one solution on its own.
  4. Update the wiki. Once the number of comments here becomes too large to easily digest at once, participants are encouraged to work on the wiki page to summarise the progress made so far, to help others get up to speed on the status of the project.
  5. Metacomments go in the discussion thread. Any non-research discussions regarding the project (e.g. organisational suggestions, or commentary on the current progress) should be made at the discussion thread.
  6. Be polite and constructive, and make your comments as easy to understand as possible. Bear in mind that the mathematical level and background of participants may vary widely.

Have fun!

June 24, 2012

Polymath7 research threads 3: the Hot Spots Conjecture

Filed under: hot spots,research — Terence Tao @ 7:21 pm

It’s once again time to roll over the research thread for the Polymath7Hot Spots” conjecture, as the previous research thread has again become full.

As the project moves into a more mature stage, with most of the “low-hanging fruit” already collected, progress is now a bit less hectic, but our understanding of the problem is improving.  For instance, in the previous thread, the relationship between two different types of arguments to obtain monotonicity of eigenfunctions – namely the coupled Brownian motion methods of Banuelos and Burdzy, and an alternate argument based on vector-valued maximum principles – was extensively discussed, and it is now fairly clear that the two methods yield a more or less equivalent set of results (e.g. monotonicity for obtuse triangles with Neumann conditions, or acute triangles with two Neumann and one Dirichlet side).  Unfortunately, for scalene triangles it was observed that the behaviour of eigenfunctions near all three vertices basically preclude any reasonable monotonicity property from taking place (in particular, the conjecture in the preceding thread in this regard was false).  This is something of a setback, but perhaps there is some other monotonicity-like property which could still hold for scalene acute triangles, and which would imply the hot spots conjecture for these triangles.  We do now have a number of accurate numerical representations of eigenfunctions, as well as some theoretical understanding of their behaviour, especially near vertices or near better-understood triangles (such as the equilateral or isosceles right-angled triangle) so perhaps they could be used to explore some of these properties.

Another result claimed in previous threads – namely, a theoretical proof of the simplicity of the second eigenvalue – has now been completed, with fairly good bounds on the spectral gap, which looks like a useful thing to have.

It was realised that a better understanding of the geometry of the nodal line would be quite helpful – in particular its convexity, which would yield the hot spots conjecture on one side of the nodal line at least.   We did establish one partial result in this direction, namely that the nodal line cannot hit the same edge of the triangle twice, but must instead straddle two edges of the triangle (or a vertex and an opposing edge, though presumably this case only occurs for isosceles triangles).  Unfortunately, more control on the nodal line is needed.

In the absence of a definitive theoretical approach to the problem, the other main approach is via rigorous numerics – to obtain, for a sufficiently dense mesh of test triangles, a collection of numerical approximations to second eigenfunctions which are provably close (in a suitable norm) to a true second eigenfunction, and whose extrema (or near-extrema) only occur at vertices (or near-vertices).  In principle, this sort of information would be good enough to rigorous establish the hot spots conjecture for such a test triangle as well as nearby perturbations of that triangle.  The details of this approach, though, are still being worked out.  (And given that they could be a bit messy, it may well be a good idea to not proceed too prematurely with the numerical approach, in case some better approach is discovered in the near future).  One proposal is to focus on a single typical triangle (e.g. the 40-60-80 triangle) as a test case in order to fix parameters.

There was also some further exploration of whether reflection methods could be pushed further.   It was pointed out that even in the very simple case of the unit interval [0,1], it is not obvious (even heuristically) from reflection arguments why the hot spots conjecture should be true.  Reflecting around a vertex whose angle does not go evenly into \pi has created a number of technical difficulties which seem to so far be unsatisfactorily addressed (but perhaps getting an alternate proof of hot spots in the model cases where reflection does work, i.e. the 30-60-90, 45-45-90, and 60-60-60 triangles, would be worthwhile).

 

June 15, 2012

Polymath7 research threads 2: the Hot Spots Conjecture

Filed under: hot spots,research — Terence Tao @ 9:48 pm

The previous research thread for the Polymath7Hot Spots Conjecture” project has once again become quite full, so it is again time to roll it over and summarise the progress so far.

Firstly, we can update the map of parameter space from the previous thread to incorporate all the recent progress (including some that has not quite yet been completed):

This map reflects the following new progress:

  1. We now have (or will soon have) a rigorous proof of the simplicity of the second Neumann eigenvalue for all non-equilateral acute triangles (this is the dotted region), thus finishing off the first part of the hot spots conjecture in all cases.  The main idea here is to combine upper bounds on the second eigenvalue \lambda_2 (obtained by carefully choosing trial functions for the Rayleigh quotient), with lower bounds on the sum \lambda_2+\lambda_3 of the second and third eigenvalues, obtained by using a variety of lower bounds coming from reference triangles such as the equilateral or isosceles right triangle.  This writeup contains a treatment of those triangles close to the equilateral triangle, and it is expected that the other cases can be handled similarly.
  2. For super-equilateral triangles (the yellow edges) it is now known that the extreme points of the second eigenfunction occur at the vertices of the base, by cutting the triangle in half to obtain a mixed Dirichlet-Neumann eigenvalue problem, and then using the synchronous Brownian motion coupling method of Banuelos and Burdzy to show that certain monotonicity properties of solutions to the heat equation are preserved.  This fact can also be established via a vector-valued maximum principle.  Details are on the wiki.
  3. Using stability of eigenfunctions and eigenvalues with respect to small perturbations (at least when there is a spectral gap), one can extend the known results for right-angled and non-equilateral triangles to small perturbations of these triangles (the orange region).  For instance, the stability results of Banuelos and Pang already give control of perturbed eigenfunctions in the uniform norm; since for right-angled triangles and non-equilateral triangles, the extrema only occur at vertices, and from Bessel expansion and uniform C^2 bounds we know that for any perturbed eigenfunction, the vertices will still be local extrema at least (with a uniform lower bound on the region in which they are extremisers), we conclude that the global extrema will still only occur at vertices for perturbations.
  4. Some variant of this argument should also work for perturbations of the equilateral triangle (the dark blue region).  The idea here is that the second eigenfunction of a perturbed equilateral triangle should still be close (in, say, the uniform norm) to some second eigenfunction of the equilateral triangle.  Understanding the behaviour of eigenfunctions nearly equilateral triangles more precisely seems to be a useful short-term goal to pursue next in this project.

But there is also some progress that is not easily representable on the above map.  It appears that the nodal line \{u=0\} of the second eigenfunction u may play a key role.  By using reflection arguments and known comparison inequalities between Dirichlet and Neumann eigenvalues, it was shown that the nodal line cannot hit the same edge twice, and thus must straddle two distinct edges (or a vertex and an opposing edge).   (The argument is sketched on the wiki.) If we can show some convexity of the nodal line, this should imply that the vertex straddled by the nodal line is a global extremum by the coupled Brownian motion arguments, and the only extremum on this side of the nodal line, leaving only the other side of the nodal line (with two vertices rather than one) to consider.

We’re now also getting some numerical data on eigenvalues, eigenfunctions, and the spectral gap.  The spectral gap looks reasonably large once one is away from the degenerate triangles and the equilateral triangle, which bodes well for an attempt to resolve the conjecture for acute angled triangles by rigorous numerics and perturbation theory.  The eigenfunctions also look reassuringly monotone in various directions, which suggests perhaps some conjectures to make  in this regard (e.g. are eigenfunctions always monotone along the direction parallel to the longest side?).

This isn’t a complete summary of the discussion thus far – other participants are encouraged to summarise anything else that happened that bears repeating here.

June 12, 2012

Polymath7 research thread 1: The Hot Spots Conjecture

Filed under: hot spots,research — Terence Tao @ 8:58 pm

The previous research thread for the Polymath7 project “the Hot Spots Conjecture” is now quite full, so I am now rolling it over to a fresh thread both to summarise the progress thus far, and to make it a bit easier to catch up on the latest developments.

The objective of this project is to prove that for an acute angle triangle ABC, that

  1. The second eigenvalue of the Neumann Laplacian is simple (unless ABC is equilateral); and
  2. For any second eigenfunction of the Neumann Laplacian, the extremal values of this eigenfunction are only attained on the boundary of the triangle.  (Indeed, numerics suggest that the extrema are only attained at the corners of a side of maximum length.)

To describe the progress so far, it is convenient to draw the following “map” of the parameter space.  Observe that the conjecture is invariant with respect to dilation and rigid motion of the triangle, so the only relevant parameters are the three angles \alpha,\beta,\gamma of the triangle.  We can thus represent any such triangle as a point (\alpha/\pi,\beta/\pi,\gamma/\pi) in the region \{ (x,y,z): x+y+z=1, x,y,z > 0 \}.  The parameter space is then the following two-dimensional triangle:

Thus, for instance

  1. A,N,P represent the degenerate obtuse triangles (with two angles zero, and one angle of 180 degrees);
  2. B,F,O represent the degenerate acute isosceles triangles (with two angles 90 degrees, and one angle zero);
  3. C,E,G,I,L,M represent the various permutations of the 30-60-90 right-angled triangle;
  4. D,J,K represent the isosceles right-angled triangles (i.e. the 45-45-90 triangles);
  5. H represents the equilateral triangle (i.e. the 60-60-60 triangle);
  6. The acute triangles form the interior of the region BFO, with the edges of that region being the right-angled triangles, and the exterior being the obtuse triangles;
  7. The isosceles triangles form the three line segments NF, BP, AO.  Sub-equilateral isosceles triangles (with apex angle smaller than 60 degrees) comprise the open line segments BH,FH,OH, while super-equilateral isosceles triangles (with apex angle larger than 60 degrees) comprise the complementary line segments AH, NH, PH.

Of course, one could quotient out by permutations and only work with one sixth of this diagram, such as ABH (or even BDH, if one restricted to the acute case), but I like seeing the symmetry as it makes for a nicer looking figure.

Here’s what we know so far with regards to the hot spots conjecture:

  1. For obtuse or right-angled triangles (the blue shaded region in the figure), the monotonicity results of Banuelos and Burdzy show that the second claim of the hot spots conjecture is true for at least one second eigenfunction.
  2. For any isosceles non-equilateral triangle, the eigenvalue bounds of Laugesen and Siudeja show that the second eigenvalue is simple (i.e. the first part of the hot spots conjecture), with the second eigenfunction being symmetric around the axis of symmetry for sub-equilateral triangles and anti-symmetric for super-equilateral triangles.
  3. As a consequence of the above two facts and a reflection argument found in the previous research thread, this gives the second part of the hot spots conjecture for sub-equilateral triangles (the green line segments in the figure). In this case, the extrema only occur at the vertices.
  4. For equilateral triangles (H in the figure), the eigenvalues and eigenfunctions can be computed exactly; the second eigenvalue has multiplicity two, and all eigenfunctions have extrema only at the vertices.
  5. For sufficiently thin acute triangles (the purple regions in the figure), the eigenfunctions are almost parallel to the sector eigenfunction given by the zeroth Bessel function; this in particular implies that they are simple (since otherwise there would be a second eigenfunction orthogonal to the sector eigenfunction).  Also, a more complicated argument found in the previous research thread shows in this case that the extrema can only occur either at the pointiest vertex, or on the opposing side.

So, as the figure shows, there has been some progress on the problem, but there are still several regions of parameter space left to eliminate.  It may be possible to use perturbation arguments to extend validity of the hot spots conjecture beyond the known regions by some quantitative extent, and then use numerical verification to finish off the remainder.  (It appears that numerics work well for acute triangles once one has moved away from the degenerate cases B,F,O.)

The figure also suggests some possible places to focus attention on, such as:

  1. Super-equilateral acute triangles (the line segments DH, GH, KH).  Here, we know the second eigenfunction is simple (and anti-symmetric).
  2. Nearly equilateral triangles (the region near H).  The perturbation theory for the equilateral triangle could be non-trivial due to the repeated eigenvalue here.
  3. Nearly isosceles right-angled triangles (the regions near D,G,K).  Again, the eigenfunction theory for isosceles right-angled triangles is very explicit, but this time the eigenvalue is simple and perturbation theory should be relatively straightforward.
  4. Nearly 30-60-90 triangles (the regions near C,E,G,I,L,M).  Again, we have an explicit simple eigenfunction in the 30-60-90 case and an analysis should not be too difficult.

There are a number of stretching techniques (such as in the Laugesen-Siudeja paper) which are good for controlling how eigenvalues deform with respect to perturbations, and this may allow us to rigorously establish the first part of the hot spots conjecture, at least, for larger portions of the parameter space.

As for numerical verification of the second part of the conjecture, it appears that we have good finite element methods that seem to give accurate results in practice, but it remains to find a way to generate rigorous guarantees of accuracy and stability with respect to perturbations.  It may be best to focus on the super-equilateral acute isosceles case first, as there is now only one degree of freedom in the parameter space (the apex angle, which can vary between 60 and 90 degrees) and also a known anti-symmetry in the eigenfunction, both of which should cut down on the numerical work required.

I may have missed some other points in the above summary; please feel free to add your own summaries or other discussion below.

July 19, 2011

Minipolymath3 project: 2011 IMO

Filed under: research — Terence Tao @ 8:00 pm

This post marks the official opening of the mini-polymath3 project to solve a problem from the 2011 IMO.  I have decided to use Q2, in part to see how the polymath format would cope with a more geometrically themed problem.

Problem 2.  Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. A windmill is a process that starts with a line \ell going through a single point P \in S. The line rotates clockwise about the pivot P until the first time that the line meets some other point Q belonging to S. This point Q takes over as the new pivot, and the line now rotates clockwise about Q, until it next meets a point of S. This process continues indefinitely.
Show that we can choose a point P in S and a line \ell going through P such that the resulting windmill uses each point of S as a pivot infinitely many times.
The comments to this post shall serve as the research thread for the project, in which participants are encouraged to post their thoughts and comments on the problem, even if (or especially if) they are only partially conclusive.  Participants are also encouraged to visit the discussion thread for this project, and also to visit and work on the wiki page to organise the progress made so far.
This project will follow the general polymath rules.  In particular:
  1. All are welcome. Everyone (regardless of mathematical level) is welcome to participate.  Even very simple or “obvious” comments, or comments that help clarify a previous observation, can be valuable.
  2. No spoilers! It is inevitable that solutions to this problem will become available on the internet very shortly.  If you are intending to participate in this project, I ask that you refrain from looking up these solutions, and that those of you have already seen a solution to the problem refrain from giving out spoilers, until at least one solution has already been obtained organically from the project.
  3. Not a race. This is not intended to be a race between individuals; the purpose of the polymath experiment is to solve problems collaboratively rather than individually, by proceeding via a multitude of small observations and steps shared between all participants.   If you find yourself tempted to work out the entire problem by yourself in isolation, I would request that you refrain from revealing any solutions you obtain in this manner until after the main project has reached at least one solution on its own.
  4. Update the wiki. Once the number of comments here becomes too large to easily digest at once, participants are encouraged to work on the wiki page to summarise the progress made so far, to help others get up to speed on the status of the project.
  5. Metacomments go in the discussion thread. Any non-research discussions regarding the project (e.g. organisational suggestions, or commentary on the current progress) should be made at the discussion thread.
  6. Be polite and constructive, and make your comments as easy to understand as possible. Bear in mind that the mathematical level and background of participants may vary widely.

Have fun!

October 27, 2009

(Research thread V) Determinstic way to find primes

Filed under: finding primes,research — Terence Tao @ 10:25 pm

It’s probably time to refresh the previous thread for the “finding primes” project, and to summarise the current state of affairs.

The current goal is to find a deterministic way to locate a prime in an interval [z,2z] in time that breaks the “square root barrier” of \sqrt(z) (or more precisely, z^{1/2+o(1)}).  Currently, we have two ways to reach that barrier:

  1. Assuming the Riemann hypothesis, the largest prime gap in [z,2z] is of size z^{1/2+o(1)}.  So one can simply test consecutive numbers for primality until one gets a hit (using, say, the AKS algorithm, any number of size z can be tested for primality in time z^{o(1)}.
  2. The second method is due to Odlyzko, and does not require the Riemann hypothesis.  There is a contour integration formula that allows one to write the prime counting function \pi(z) up to error z^{1+o(1)}/T in terms of an integral involving the Riemann zeta function over an interval of length O(T), for any 1 \leq T \leq z.  The latter integral can be computed to the required accuracy in time about z^{o(1)} T.  With this and a binary search it is not difficult to locate an interval of width z^{1+o(1)}/T that is guaranteed to contain a prime in time z^{o(1)} T.  Optimising by choosing T = z^{1/2} and using a sieve (or by testing the elements for primality one by one), one can then locate that prime in time z^{1/2+o(1)}.

Currently we have one promising approach to break the square root barrier, based on the polynomial method, but while individual components of this approach fall underneath the square root barrier, we have not yet been able to get the whole thing below (or even matching) the square root.  I will sketch the approach (as far as I understand it) below; right now we are needing some shortcuts (e.g. FFT, fast matrix multiplication, that sort of thing) that can cut the run time further.

(more…)

August 28, 2009

(Research Thread IV) Determinstic way to find primes

Filed under: finding primes,research — Terence Tao @ 1:43 am
Tags:

This post will be somewhat abridged due to my traveling schedule.

The previous research thread for the “finding primes” project is now getting quite full, so I am opening up a fresh thread to continue the project.

Currently we are up against the “square root barrier”: the fastest time we know of to find a k-digit prime is about \sqrt{10^k} (up to \exp(o(k)) factors), even in the presence of a factoring oracle (though, thanks to a method of Odlyzko, we no longer need the Riemann hypothesis).  We also have a “generic prime” razor that has eliminated (or severely limited) a number of potential approaches.

One promising approach, though, proceeds by transforming the “finding primes” problem into a “counting primes” problem.  If we can compute prime counting function \pi(x) in substantially less than \sqrt{x} time, then we have beaten the square root barrier.

Currently we have a way to compute the parity (least significant bit) of \pi(x) in time x^{1/2+o(1)}, and there is hope to improve this (especially given the progress on the toy problem of counting square-frees less than x).  There are some variants that also look promising, for instance to work in polynomial extensions of finite fields (in the spirit of the AKS algorithm) and to look at residues of \pi(x) in other moduli, e.g. \pi(x) mod 3, though currently we can’t break the x^{2/3+o(1)} barrier for that particular problem.

August 13, 2009

(Research Thread III) Deterministic way to find primes

Filed under: finding primes,research — Terence Tao @ 5:10 pm
Tags:

This is a continuation of Research Thread II of the “Finding primes” polymath project, which is now full.  It seems that we are facing particular difficulty breaching the square root barrier, in particular the following problems remain open:

  1. Can we deterministically find a prime of size at least n in o(\sqrt{n}) time (assuming hypotheses such as RH)?  Assume one has access to a factoring oracle.
  2. Can we deterministically find a prime of size at least n in O(n^{1/2+o(1)}) time unconditionally (in particular, without RH)? Assume one has access to a factoring oracle.

We are still in the process of weighing several competing strategies to solve these and related problems.  Some of these have been effectively eliminated, but we have a number of still viable strategies, which I will attempt to list below.  (The list may be incomplete, and of course totally new strategies may emerge also.  Please feel free to elaborate or extend the above list in the comments.)

Strategy A: Find a short interval [x,x+y] such that \pi(x+y) - \pi(x) > 0, where \pi(x) is the number of primes less than x, by using information about the zeroes \rho of the Riemann zeta function.

Comment: it may help to assume a Siegel zero (or, at the other extreme, to assume RH).

Strategy B: Assume that an interval [n,n+a] consists entirely of u-smooth numbers (i.e. no prime factors greater than u) and somehow arrive at a contradiction.  (To break the square root barrier, we need a = o(\sqrt{u}), and to stop the factoring oracle from being ridiculously overpowered, n should be subexponential size in u.)

Comment: in this scenario, we will have n/p close to an integer for many primes between \sqrt{u} and u, and n/p far from an integer for all primes larger than u.

Strategy C: Solve the following toy problem: given n and u, what is the distance to the closest integer to n which contains a factor comparable to u (e.g. in [u,2u])?  [Ideally, we want a prime factor here, but even the problem of getting an integer factor is not fully understood yet.]  Beating \sqrt{u} here is analogous to breaking the square root barrier in the primes problem.

Comments:

  1. The trivial bound is u/2 – just move to the nearest multiple of u to n.  This bound can be attained for really large n, e.g. n =(2u)! + u/2.  But it seems we can do better for small n.
  2. For u \leq n \leq 2u, one trivially does not have to move at all.
  3. For 2u \leq n \leq u^2, one has an upper bound of O(n/u), by noting that having a factor comparable to u is equivalent to having a factor comparable to n/u.
  4. For n \sim u^2, one has an upper bound of O(\sqrt{u}), by taking x^2 to be the first square larger than n, y^2 to be the closest square to x^2-n, and noting that (x-y)(x+y) has a factor comparable to u and is within O(\sqrt{u}) of n.  (This paper improves this bound to O(u^{0.4}) conditional on a strong exponential sum estimate.)
  5. For n=poly(u), it may be possible to take a dynamical systems approach, writing n base u and incrementing or decrementing u and hope for some equidistribution.   Some sort of “smart” modification of u may also be effective.
  6. There is a large paper by Ford devoted to this sort of question.

Strategy D. Find special sequences of integers that are known to have special types of prime factors, or are known to have unusually high densities of primes.

Comment. There are only a handful of explicitly computable sparse sequences that are known unconditionally to capture infinitely many primes.

Strategy E. Find efficient deterministic algorithms for finding various types of “pseudoprimes” – numbers which obey some of the properties of being prime, e.g. 2^{n-1}=1 \hbox{ mod } n.  (For this discussion, we will consider primes as a special case of pseudoprimes.)

Comment. For the specific problem of solving 2^{n-1}=1 \hbox{ mod } n there is an elementary observation that if n obeys this property, then 2^n-1 does also, which solves this particular problem; but this does not indicate how to, for instance, have 2^{n-1}=1 \hbox{ mod } n and 3^{n-1}=1 \hbox{ mod } n obeyed simultaneously.

As always, oversight of this research thread is conducted at the discussion thread, and any references and detailed computations should be placed at the wiki.

Next Page »

Blog at WordPress.com.