Category Archive

You are currently browsing the category archive for the ‘question’ category.

Mini-polymath3 begins in 24 hours

18 July, 2011 in admin, polymath | Tags: | by | 1 comment

Just a reminder that the mini-polymath3 project begins in 24 hours, on July 19, 8pm UTC.

Mini-polymath 3 time and date

28 June, 2011 in admin, polymath | Tags: | by | 1 comment

Following the results from the recent poll on this blog, the mini-polymath3 project (which will focus on one of the problems from the 2011 IMO) will start at July 19 8pm UTC, and be run concurrently on this blog, on the polymath wiki, and on the polymath blog.

Mini-polymath 3: 2011 IMO question

9 June, 2011 in admin, polymath | Tags: | by | 5 comments

In the last two years, I ran a “mini-polymath” project to solve one of the problems of that year’s International Mathematical Olympiad (IMO).  This year, the IMO is being held in the Netherlands, with the problems being released on July 18 and 19, and I am planning to once again select a question (most likely the last question Q6, but I’ll exercise my discretion on which problem to select once I see all of them).

The format of the last year’s mini-polymath project seemed to work well, so I am inclined to simply repeat that format without much modification this time around, in order to collect a consistent set of data about these projects.  Thus, unles the plan changes, the project will start at a pre-arranged time and date, with plenty of advance notice, and be run simultaneously on three different sites: a “research thread” over at the polymath blog for the problem solving process, a “discussion thread” over at this blog for any meta-discussion about the project, and a wiki page at the polymath wiki to record the progress already made at the research thread.  (Incidentally, there is a current discussion at the wiki about the logo for that site; please feel free to chip in your opinion on the various proposed icons.)  The project will follow the usual polymath rules (as summarised for instance in the 2010 mini-polymath thread).

There are some kinks with our format that still need to be worked out, unfortunately; the two main ones that keep recurring in previous feedback are (a) there is no way to edit or preview comments without the intervention of one of the blog maintainers, and (b) even with comment threading, it is difficult to keep track of all the multiple discussions going on at once.  It is conceivable that we could use a different forum than the WordPress-based blogs we have been using for previous projects for this mini-polymath to experiment with other software that may help ameliorate (a) and (b) (though any alternative site should definitely have the ability to support some sort of TeX, and should be easily accessible by polymath participants, without the need for a cumbersome registration process); if there are any suggestions for such alternatives, I would be happy to hear about them in the comments to this post.  (Of course, any other comments germane to the polymath or mini-polymath projects would also be appropriate for the comment thread.)

The other thing to do at this early stage is set up a poll for the start time for the project (and also to gauge interest in participation).  For ease of comparison I am going to use the same four-hour time slots as for the 2010 poll.  All times are in Coordinated Universal Time (UTC), which is essentially the same as GMT; conversions between UTC and local time zones can for instance be found on this web site.   For instance, the Netherlands are at UTC+2, and so July 19 4m UTC (say) would be July 19 6pm in Netherlands local time.  (I myself will be at UTC-7.)

Rohlin’s problem on strongly mixing systems

9 March, 2011 in expository, math.DS, math.PR, question | Tags: , , | by | 7 comments

Let {G = (G,+)} be an abelian countable discrete group. A measure-preserving {G}-system {X = (X, {\mathcal X}, \mu, (T_g)_{g \in G})} (or {G}-system for short) is a probability space {(X, {\mathcal X}, \mu)}, equipped with a measure-preserving action {T_g: X \rightarrow X} of the group {G}, thus

\displaystyle \mu( T_g(E) ) = \mu(E)

for all {E \in {\mathcal X}} and {g \in G}, and

\displaystyle T_g T_h = T_{g+h}

for all {g, h \in G}, with {T_0} equal to the identity map. Classically, ergodic theory has focused on the cyclic case {G={\bf Z}} (in which the {T_g} are iterates of a single map {T = T_1}, with elements of {G} being interpreted as a time parameter), but one can certainly consider actions of other groups {G} also (including continuous or non-abelian groups).

A {G}-system is said to be strongly {2}-mixing, or strongly mixing for short, if one has

\displaystyle \lim_{g \rightarrow \infty} \mu( A \cap T_g B ) = \mu(A) \mu(B)

for all {A, B \in {\mathcal X}}, where the convergence is with respect to the one-point compactification of {G} (thus, for every {\epsilon > 0}, there exists a compact (hence finite) subset {K} of {G} such that {|\mu(A \cap T_g B) - \mu(A)\mu(B)| \leq \epsilon} for all {g \not \in K}).

Similarly, we say that a {G}-system is strongly {3}-mixing if one has

\displaystyle \lim_{g,h,h-g \rightarrow \infty} \mu( A \cap T_g B \cap T_h C ) = \mu(A) \mu(B) \mu(C)

for all {A,B,C \in {\mathcal X}}, thus for every {\epsilon > 0}, there exists a finite subset {K} of {G} such that

\displaystyle |\mu( A \cap T_g B \cap T_h C ) - \mu(A) \mu(B) \mu(C)| \leq \epsilon

whenever {g, h, h-g} all lie outside {K}.

It is obvious that a strongly {3}-mixing system is necessarily strong {2}-mixing. In the case of {{\bf Z}}-systems, it has been an open problem for some time, due to Rohlin, whether the converse is true:

Problem 1 (Rohlin’s problem) Is every strongly mixing {{\bf Z}}-system necessarily strongly {3}-mixing?

This is a surprisingly difficult problem. In the positive direction, a routine application of the Cauchy-Schwarz inequality (via van der Corput’s inequality) shows that every strongly mixing system is weakly {3}-mixing, which roughly speaking means that {\mu(A \cap T_g B \cap T_h C)} converges to {\mu(A) \mu(B) \mu(C)} for most {g, h \in {\bf Z}}. Indeed, every weakly mixing system is in fact weakly mixing of all orders; see for instance this blog post of Carlos Matheus, or these lecture notes of myself. So the problem is to exclude the possibility of correlation between {A}, {T_g B}, and {T_h C} for a small but non-trivial number of pairs {(g,h)}.

It is also known that the answer to Rohlin’s problem is affirmative for rank one transformations (a result of Kalikow) and for shifts with purely singular continuous spectrum (a result of Host; note that strongly mixing systems cannot have any non-trivial point spectrum). Indeed, any counterexample to the problem, if it exists, is likely to be highly pathological.

In the other direction, Rohlin’s problem is known to have a negative answer for {{\bf Z}^2}-systems, by a well-known counterexample of Ledrappier which can be described as follows. One can view a {{\bf Z}^2}-system as being essentially equivalent to a stationary process {(x_{n,m})_{(n,m) \in {\bf Z}^2}} of random variables {x_{n,m}} in some range space {\Omega} indexed by {{\bf Z}^2}, with {X} being {\Omega^{{\bf Z}^2}} with the obvious shift map

\displaystyle T_{(g,h)} (x_{n,m})_{(n,m) \in {\bf Z}^2} := (x_{n-g,m-h})_{(n,m) \in {\bf Z}^2}.

In Ledrappier’s example, the {x_{n,m}} take values in the finite field {{\bf F}_2} of two elements, and are selected at uniformly random subject to the “Pascal’s triangle” linear constraints

\displaystyle x_{n,m} = x_{n-1,m} + x_{n,m-1}.

A routine application of the Kolmogorov extension theorem allows one to build such a process. The point is that due to the properties of Pascal’s triangle modulo {2} (known as Sierpinski’s triangle), one has

\displaystyle x_{n,m} = x_{n-2^k,m} + x_{n,m-2^k}

for all powers of two {2^k}. This is enough to destroy strong {3}-mixing, because it shows a strong correlation between {x}, {T_{(2^k,0)} x}, and {T_{(0,2^k)} x} for arbitrarily large {k} and randomly chosen {x \in X}. On the other hand, one can still show that {x} and {T_g x} are asymptotically uncorrelated for large {g}, giving strong {2}-mixing. Unfortunately, there are significant obstructions to converting Ledrappier’s example from a {{\bf Z}^2}-system to a {{\bf Z}}-system, as pointed out by de la Rue.

In this post, I would like to record a “finite field” variant of Ledrappier’s construction, in which {{\bf Z}^2} is replaced by the function field ring {{\bf F}_3[t]}, which is a “dyadic” (or more precisely, “triadic”) model for the integers (cf. this earlier blog post of mine). In other words:

Theorem 2 There exists a {{\bf F}_3[t]}-system that is strongly {2}-mixing but not strongly {3}-mixing.

The idea is much the same as that of Ledrappier; one builds a stationary {{\bf F}_3[t]}-process {(x_n)_{n \in {\bf F}_3[t]}} in which {x_n \in {\bf F}_3} are chosen uniformly at random subject to the constraints

\displaystyle x_n + x_{n + t^k} + x_{n + 2t^k} = 0 \ \ \ \ \ (1)

for all {n \in {\bf F}_3[t]} and all {k \geq 0}. Again, this system is manifestly not strongly {3}-mixing, but can be shown to be strongly {2}-mixing; I give details below the fold.

As I discussed in this previous post, in many cases the dyadic model serves as a good guide for the non-dyadic model. However, in this case there is a curious rigidity phenomenon that seems to prevent Ledrappier-type examples from being transferable to the one-dimensional non-dyadic setting; once one restores the Archimedean nature of the underlying group, the constraints (1) not only reinforce each other strongly, but also force so much linearity on the system that one loses the strong mixing property.

Read the rest of this entry »

Polymath3 now active

30 September, 2010 in math.CO, polymath | Tags: , , | by | 7 comments

Gil Kalai has officially started the Polymath3 project (Polynomial Hirsch conjecture) with a research thread at his blog.

The original aim of this project is to prove the polynomial Hirsch conjecture, which is a conjecture in the combinatorial geometry of polytopes.  However, there is a reduction due to Eisenbrand, Hahnle, Razborov, and Rothvoss that would deduce this conjecture from a purely combinatorial conjecture, which can be stated as follows.

Combinatorial polynomial Hirsch conjecture. Let {\mathcal F}_1,\ldots,{\mathcal F}_t be non-empty collections of subsets of \{1,\ldots,n\} with the following properties:

  1. (Disjointness) {\mathcal F}_i \cap {\mathcal F}_j = \emptyset for every i \neq j.
  2. (Connectedness)  If 1 \leq i < j < k \leq t and A \in {\mathcal F}_i, B \in {\mathcal F}_ k, there exists C \in {\mathcal F}_j such that A \cap B \subset C.

Then t is of polynomial size in n (i.e. t = O(n^{O(1)})).

For instance, when n=3, one can obtain such a family with t=6, e.g.

{\mathcal F}_1 = \{ \emptyset\}, {\mathcal F}_2 = \{ \{1\}\}, {\mathcal F}_3 = \{\{1,2\}\}, {\mathcal F}_4 = \{\{1,2,3\}\},

{\mathcal F}_5 = \{\{2,3\}\}, {\mathcal F}_6 = \{\{3\}\};

one can show that this is the best possible value of t for this choice of n.  The best possible value of t for n=4 is still not worked out; it is between 8 and 11.

One appealing thing about this problem is that there is a simple elementary argument that gives the bound t \leq n^{\log_2 n + 1} for all n \geq 2; and so in some sense one is “only a logarithm away” from proving the conjecture.  Anyway, the project is just starting, and does not require any particularly specialised background, so anyone who may be interested in this problem one may want to take a look at the research thread.

Deterministic methods to find primes

21 September, 2010 in math.NT, paper, polymath | Tags: , , | by | 12 comments

I’ve uploaded to the arXiv the polymath research paper “Deterministic methods to find primes“, which is the outcome of the Polymath4 collaborative mathematics project, and has been submitted to Mathematics of Computation.

The objective of this paper was to find fast deterministic algorithms to solve the following problem:

Given a (large) integer x, find a prime p larger than x.

Thanks to the AKS algorithm, a number of size O(x) can be deterministically tested for primality in time O( \log^{O(1)} x ) = O( x^{o(1)} ).   By Bertrand’s postulate, there is always at least one prime between x and 2x; by testing each one of these integers in turn for primality, one can thus obtain a deterministic algorithm to find primes in time O( x^{1+o(1)}).

But one should be able to do much better.  For comparison, if probabilistic algorithms are allowed, then by randomly selecting integers between x and 2x to test for primality, it is easy to see from the prime number theorem that one will succeed in obtaining a prime with high probability in time O( \log^{O(1)} x ) = O( x^{o(1)} ).  However, after some effort we were not able to “derandomise” this algorithm to create any reasonable deterministic counterpart.  Nevertheless, we conjecture that a deterministic algorithm with run time O( x^{o(1)}) exists.  Such algorithms can be easily obtained if one assumes some standard conjectures regarding the primes (e.g. Cramer’s conjecture on prime gaps), but we do not know of any deterministic algorithms which can be unconditionally proved to run in time O( x^{o(1)}).

Currently, the best known deterministic algorithm is due to Lagarias and Odlyzko, and has a run time of O( x^{1/2+o(1)}).  Roughly speaking, it is based on the ability to compute the prime counting function \pi(x) in time O( x^{1/2+o(1)} ); once one has this function, one can detect which intervals contain primes or not, and then starting from Bertrand’s postulate and performing a binary search one can then locate a prime.  The Lagarias-Odlyzko argument is based on approximating \pi(x) by a certain integral of the Riemann zeta function, which one then approximates in turn by quadrature.

We conjecture that one should be able to compute \pi(x) in faster time, and in particular in time O(x^{1/2-c+o(1)}) for some c>0.  Unfortunately, we were not able to achieve this; however, we do have a non-trivial method to compute the parity \pi(x) \hbox{ mod } 2 of \pi(x) in such a time; a bit more generally (and oversimplifying a little bit), we can compute various projections \sum_{p \leq x} t^p \hbox{ mod } 2, g(t) of the prime polynomial \sum_{p \leq x} t^p modulo some small polynomials g.  This seems close to being able to achieve the goal of detecting whether primes exist in a given interval, but unfortunately some additional work seems to be needed in that area.  Still, the methods used to get the parity seem to be interesting (involving the Dirichlet hyperbola method, a piecewise approximation of the hyperbola, and the Strassen fast multiplication algorithm), and these techniques might be useful for some other problems.

Roughly speaking, the idea to compute the parity of \pi(x) \hbox{ mod } 2 is as follows.  The first observation is that, for square-free n, the number \tau(n) of divisors of n is equal to 2 when n is a prime, and a multiple of 4 otherwise.  So to compute the parity of \pi(x), it suffices to compute \sum_{n \leq x} \tau(n) modulo 4 (or more precisely, the restriction of this sum to squarefree n).

The restriction to squarefree numbers turns out to be relatively easy to handle, so we ignore it.  Since \tau(n) = \sum_{a,b: ab=n} 1, we can rewrite

\sum_{n \leq x} \tau(n) = \sum_{a,b: ab \leq x} 1.

So it suffices to find an efficient way to count the number of lattice points below the hyperbola \{ (a,b): ab = x \}.

The classic way to do this is via the Dirichlet hyperbola method.  This lets one rewrite the above expression as

2 \sum_{a \leq \sqrt{x}} \lfloor \frac{x}{a} \rfloor - \lfloor \sqrt{x}\rfloor^2

(assuming x is not a perfect square, where \lfloor x \rfloor is the greatest integer function).  One can then compute this quantity in time O(x^{1/2+o(1)}) without difficulty.

To improve this to O(x^{1/2-c+o(1)}), we used some ideas of Vinogradov, based on using Diophantine approximation to find moderately long arithmetic progressions on which the map a \mapsto \lfloor \frac{x}{a} \rfloor is linear, and thus easily summable.

The same method extends to the polynomial setting, though now, instead of summing an arithmetic progression, one has to find an efficient way to sum quadratic sums such as \sum_{n=1}^N t^{an^2+bn+c}.  This turns out to be possible by expressing this sum as a matrix product and then using fast matrix multiplication algorithms.

There is still some scope to improve the results and methods further; Ernie Croot is pursuing this with two undergraduate students, David Hollis and David Lowry,

Mini-polymath2 discussion thread

8 July, 2010 in admin, polymath | by | 26 comments

I’ve just opened the Mini-polymath2 project over at the polymath blog.  I decided to use Q5 from the 2010 IMO in the end, rather than Q6, as it seems to be a little bit more challenging and interesting.

This post will serve as the discussion thread of the project, intended to focus all the non-research aspects of the project such as organisational matters or commentary on the progress of the project.     (Is it possible for one blog thread to “live-blog” another?) The third component of the project is the wiki page, which is intended to summarise the progress made so far on the problem.

As with mini-polymath1, I myself will be serving primarily as a moderator, and hope other participants will take the lead in the research and in keeping the wiki up-to-date.   (Ideally, once we get all the kinks in the format ironed out, it should be possible for anyone with a blog and an interested pool of participants to start their own mini-polymath project, without being overly dependent on one key contributor.)

Mini-polymath2 start time

27 June, 2010 in admin, polymath | Tags: , | by | 2 comments

In view of feedback, I have decided to start the mini-polymath2 project at 16:00 July 8 UTC, at which time I will select one of the 2010 IMO questions to solve.  The actual project will be run on the polymath blog; this blog will host the discussion threads and post-experiment analysis.

Organising mini-polymath2

21 June, 2010 in non-technical, polymath | Tags: | by | 10 comments

This is a continuation of the preceding post regarding the setting up of the mini-polymath2 project.  From the discussion, it seems that it is best to start at some fixed time, either on July 8 or July 9, to ensure an orderly opening to the project and also so that I can select which of the six questions would be most suitable for such a project.

I have set up a placeholder wiki page for the project here, though right now it is necessarily quite bare.

There wasn’t much feedback on where to host the polymath project, but I am thinking of hosting the main project over on the polymath blog, in order to take advantage of the slightly better threading format there (numbered comments and nested comments in particular, although unfortunately there is no comment editing capability), and also because it would be technically easier to have multiple moderators on that blog.   When the project begins, I will also announce it in a brief post on this blog, which can then serve as the “meta” or “discussion” page for the project.

The one thing that I need to fix before the project begins is the starting time.   I do not know exactly when the Kazakhstan local IMO organising committee will release the full list of questions, but presumably they should be available by, say, noon July 8 at Kazazhstan time (GMT+4), or about 8am July 8 GMT, which would probably be the earliest feasible starting time.   Given that I am at GMT-8, the next reasonable starting time would be about eight hours later, at 4pm July 8 GMT.  Below is a poll regarding what times participants would most prefer and least prefer, spaced at 4 hour intervals:

I’ve set it so that up to three answers may be selected.  I am also open to other suggestions regarding the starting time.  I encourage everyone who is interested in participating to select some times for the poll.  Note: the times given are with respect to GMT.  A list of some representative time zones and their UTC offsets (which are more or less equivalent to GMT offsets, modulo daylight savings issues) can be found here.

With this feedback, I should be able to select a reasonable starting time.  The previous mini-polymath was active for about 48 hours (in particular, continuing to produce alternate solutions well after the first one was posted), and I would expect something similar here.  I am hoping therefore that provided there is some effort by participants to help bring people up to speed, that one could drop in even several hours after the formal start of the project and still be able to contribute.

Future mini-polymath project: 2010 IMO Q6?

12 June, 2010 in non-technical, polymath | Tags: , | by | 15 comments

About a year ago, as an experiment, I set up on this blog a “mini-polymath” project, in which readers were invited to collaboratively solve the sixth question on the 2009 International Mathematical Olympiad (aka “the grasshopper problem”).  After two or three days of somewhat chaotic activity, multiple solutions to this problem were obtained, and have been archived on this page.

In the post-mortem discussion of this experiment, it became clear that the project could have benefited from some more planning and organisation, for instance by setting up a wiki page early on to try to collect strategies, insights, partial results, etc.  Also, the project was opened without any advance warning or prior discussion, which led to an interesting but chaotic opening few hours to the project.

About a month from now, the 51st International Mathematical Olympiad will be held in Kazahkstan, with the actual problems being released on July 7 and 8.  Traditionally, the sixth problem of the Olympiad (which would thus be made public on July 8) is the hardest, and often the most interesting to solve.  So in the interest of getting another data point for the polymath process, I am thinking of setting up another mini-polymath for this question (though I of course do not know in advance what this question will be!).  But this time, I would like to try to plan things out well in advance, to see if this makes much of a difference in how the project unfolds.

So I would like to open a discussion among those readers who might be interested in such a project, regarding the logistics of such a project.  Some basic issues include:

  1. Date and time. Clearly, the project cannot start any earlier than July 8.  One could either try to fix a specific time (to within an hour, say), to officially start the project, or one could open the thread in advance of the IMO organisers releasing the questions, and just let the first person to find the questions post them to the thread, and start the clock from there.  I assume one can rely on the honour code to refrain from privately trying to solve the question before any official starting time.
  2. Location. In addition to this blog here, there is now also a dedicated polymath blog for these projects, which has some minor advantages over this one (e.g. numbered and threaded comments with wide margins).  It has fairly low levels of activity right now (though we are just starting to write up some modest progress from the ongoing Polymath4 “finding primes” project), but this may actually be a plus when running the project, to minimise cross-traffic.  Also, another benefit of the other blog is that the project can be co-administered by several people, and not just by myself.  This blog here admittedly has significantly higher traffic than the polymath blog at present, but I would certainly post a crosslink to the polymath blog if the project started.
  3. Ground rules.  The rules for the first mini-polymath project can be found here.  Basically the spirit of the rules is that the objective is not to be the first to produce an individual solution, but instead to contribute to a collective solution by sharing one’s insights, even if they are small or end up being inconclusive.  (See also Tim Gowers’ original post regarding polymath projects.)   But perhaps some tweaking to the rules may be needed.  (For instance, we may want to have some semi-official role for moderators to organise the discussion.  Ideally I would prefer not to be the sole moderator, in part because I want to see the extent to which such projects can flourish independently of one key person.)
  4. Set up.  It seems clear that we should have an official wiki page (probably a subpage from the polymath wiki) well in advance of the project actually starting (which could also be used to advertise the project beyond the usual readership of this blog).  Is there anything else which it might be useful to have in place before the project starts?
  5. Contingency planning. It may happen that for one reason or another, 2010 IMO Q6 will not turn out to be that good of a polymath problem.  I suppose it may be sensible to reserve the right to switch to, say, 2010 IMO Q5, if need be.  This might be one place where I might exercise some unilateral judgement, as it may be difficult to quickly get consensus on these sorts of issues.   I don’t know if it’s worth discussing these sorts of possibilities in advance; it may simply be better to improvise when and if some course corrections need to be made.

Anyway, I hope that this project will be interesting, and am hoping to get some good suggestions as to how make it an instructive and enjoyable experience for all.

RSS Google+ feed

  • An error has occurred; the feed is probably down. Try again later.
Follow

Get every new post delivered to your Inbox.

Join 2,321 other followers