Find a different parameter, show that it tends to infinity, and show that that implies that the discrepancy tends to infinity: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
No edit summary
Line 5: Line 5:
This is a strategy that could potentially be applied either to the general problem or to the multiplicative case. The latter would probably be easier so I shall mainly discuss that case.
This is a strategy that could potentially be applied either to the general problem or to the multiplicative case. The latter would probably be easier so I shall mainly discuss that case.


The thought behind it is that the discrepancy of a sequence is a pretty useless parameter in any kind of inductive argument. Note that in the multiplicative case, which is the one I am discussing at the moment, the discrepancy is simply the largest absolute value of any partial sum of the sequence. Now if you put together two sequences, what can you say? In order for this question to be even remotely sensible, when we talk about the discrepancy of the second sequence we must mean something like the largest drift along any segment of a HAP (where HAP is with respect to zero rather than to the point just before the second sequence starts). But knowing the discrepancy of the first sequence and the maximum drift of the second tells us virtually nothing about the discrepancy of the concatenation, since the HAPs where the maxima occur could have nothing to do with each other. And the same applies even if we put together several sequences: if we know that each sequence has a drift of 2C, say, there seems to be no way of using this information to prove that the concatenation of the sequences has drift greater than 2C.
The thought behind it is that it feels somehow as though the best multiplicative examples "ought" to be [[character-like functions|character-like]], even though in fact they are not. But perhaps one could devise a parameter with the following properties.


To be continued.
1. The parameter is as small as possible for character-like sequences.
 
2. The parameter is unbounded for character-like sequences.
 
3. The parameter can be bounded in terms of the discrepancy.
 
If we have properties 1-3, then we have a proof of EDP for multiplicative sequences, since if there were an infinite multiplicative sequence with bounded discrepancy, it would follow from 3 that the new parameter was bounded, which by 1 would imply that the parameter could be bounded for character-like sequences, contradicting 2.
 
==A proposal for a parameter==
 
Let <math>x=(x_n)</math> be a <math>\pm 1</math> sequence of length N, and for each n let <math>y_n=x_1+\dots+x_n</math> be the partial sum up to n (with <math>y_0=0</math>. For any subinterval <math>I\subset\{1,2,\dots,N\}</math> let osc(I) denote the difference between the maximum and minimum of the <math>y_n</math> with <math>n\in I</math>. For each r, define the <em>average r-drift</math> &delta;(r) of the sequence to be the average of osc(I) over all subintervals of <math>\{1,2,\dots,N\}</math> of length r, and finally let the <em>mean oscillation up to m</em> <math>\Delta(m)</math> be the weighted sum <math>(\log m)^{-1}\sum_{r=1}^mr^{-1}\delta(r)</math>.
 
==Motivation for this particular parameter==
 
The motivation for a parameter that involves oscillation can be seen in [http://thomas1111.files.wordpress.com/2010/01/seqvchar3better2c.png  this diagram], which shows the graphs of the partial sums of two multiplicative sequences. The first is the sequence obtained by sending 3 to -1 and all other primes p to 1 if they are 1 mod 3 and -1 if they are -1 mod 3. The second is one of the 500 longest possible multiplicative sequences of discrepancy at most 2. (The sequence itself can be found on the page devoted to [multiplicative sequences].)
 
The discrepancy of the first sequence is 3 rather than 2, so in that respect it is a worse sequence. However, its graph oscillates less on all distance scales except the very largest. This suggests that we might try to find a parameter with properties 1-3 by searching for a parameter that is particularly low for the first sequence and other character-like sequences.
 
Suppose we agree to take <em>some</em> weighted average of the r-drifts. Why should we take this particular one? The idea is that the graphs of the partial sums of the character-like functions have a self-similarity that means that it makes sense to look at them at several different distance scales, each larger than the previous one by a constant factor. We would like to attach equal weight to these distance scales, which suggests an average such as <math>k^{-1}(\delta(2)+\delta(4)+\dots+\delta(2^k))</math>. The particular average chosen is simply a smoother version that does not give any particular significance to one ratio such as 2.
 
==How might one prove that this parameter has Property 1?==
 
It is not hard to show that this parameter is unbounded for character-like sequences, and it can trivially be bounded by the discrepancy, so it will be useful only if we can prove that it has Property 1. At the moment it is not even clear what Property 1 means, since there are many different character-like functions, and the parameter takes different values at them. It also appears to be at least <em>locally</em> minimized at character-like sequences, in the sense that it seems difficult to change a character-like sequence at a small number of primes without increasing the parameter. But how could one use it in proofs? At the time of writing this is far from clear, but the parameter has been introduced only very recently, so perhaps it will become clearer.

Revision as of 14:35, 24 January 2010

Click here to return to the main Polymath5 page

Introduction

This is a strategy that could potentially be applied either to the general problem or to the multiplicative case. The latter would probably be easier so I shall mainly discuss that case.

The thought behind it is that it feels somehow as though the best multiplicative examples "ought" to be character-like, even though in fact they are not. But perhaps one could devise a parameter with the following properties.

1. The parameter is as small as possible for character-like sequences.

2. The parameter is unbounded for character-like sequences.

3. The parameter can be bounded in terms of the discrepancy.

If we have properties 1-3, then we have a proof of EDP for multiplicative sequences, since if there were an infinite multiplicative sequence with bounded discrepancy, it would follow from 3 that the new parameter was bounded, which by 1 would imply that the parameter could be bounded for character-like sequences, contradicting 2.

A proposal for a parameter

Let [math]\displaystyle{ x=(x_n) }[/math] be a [math]\displaystyle{ \pm 1 }[/math] sequence of length N, and for each n let [math]\displaystyle{ y_n=x_1+\dots+x_n }[/math] be the partial sum up to n (with [math]\displaystyle{ y_0=0 }[/math]. For any subinterval [math]\displaystyle{ I\subset\{1,2,\dots,N\} }[/math] let osc(I) denote the difference between the maximum and minimum of the [math]\displaystyle{ y_n }[/math] with [math]\displaystyle{ n\in I }[/math]. For each r, define the average r-drift</math> δ(r) of the sequence to be the average of osc(I) over all subintervals of [math]\displaystyle{ \{1,2,\dots,N\} }[/math] of length r, and finally let the mean oscillation up to m [math]\displaystyle{ \Delta(m) }[/math] be the weighted sum [math]\displaystyle{ (\log m)^{-1}\sum_{r=1}^mr^{-1}\delta(r) }[/math].

Motivation for this particular parameter

The motivation for a parameter that involves oscillation can be seen in this diagram, which shows the graphs of the partial sums of two multiplicative sequences. The first is the sequence obtained by sending 3 to -1 and all other primes p to 1 if they are 1 mod 3 and -1 if they are -1 mod 3. The second is one of the 500 longest possible multiplicative sequences of discrepancy at most 2. (The sequence itself can be found on the page devoted to [multiplicative sequences].)

The discrepancy of the first sequence is 3 rather than 2, so in that respect it is a worse sequence. However, its graph oscillates less on all distance scales except the very largest. This suggests that we might try to find a parameter with properties 1-3 by searching for a parameter that is particularly low for the first sequence and other character-like sequences.

Suppose we agree to take some weighted average of the r-drifts. Why should we take this particular one? The idea is that the graphs of the partial sums of the character-like functions have a self-similarity that means that it makes sense to look at them at several different distance scales, each larger than the previous one by a constant factor. We would like to attach equal weight to these distance scales, which suggests an average such as [math]\displaystyle{ k^{-1}(\delta(2)+\delta(4)+\dots+\delta(2^k)) }[/math]. The particular average chosen is simply a smoother version that does not give any particular significance to one ratio such as 2.

How might one prove that this parameter has Property 1?

It is not hard to show that this parameter is unbounded for character-like sequences, and it can trivially be bounded by the discrepancy, so it will be useful only if we can prove that it has Property 1. At the moment it is not even clear what Property 1 means, since there are many different character-like functions, and the parameter takes different values at them. It also appears to be at least locally minimized at character-like sequences, in the sense that it seems difficult to change a character-like sequence at a small number of primes without increasing the parameter. But how could one use it in proofs? At the time of writing this is far from clear, but the parameter has been introduced only very recently, so perhaps it will become clearer.

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Find_a_different_parameter,_show_that_it_tends_to_infinity,_and_show_that_that_implies_that_the_discrepancy_tends_to_infinity&oldid=2841"