Return to Answer

Using Fourier analysis in the $d$ variable, we can get the optimal upper bound. As in Tao's argument, if there is a distribution of sequences for which each pair is $r$-probably increasing, there must be a single sequence $d_i$ : such that:

$$\sum_{1\leq a <b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} >(1+ o(1)) (2r-1) k \log k$$

We may rewrite the left hand side as:

$$\sum_{1\leq a ,b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} 1_{a<b}$$

Now use the "carrying the 1" decomposition:

$$ 1_{a<b} = \frac{b}{n} - \frac{a}{n} + \frac{ a-b \mod n}{n}$$

The first two terms are pretty simple. The first term is:

$$\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} \frac{d_j}{n} = \sum_{1 \leq j \leq k} \frac{d_j}{n} \log \left( \frac{j}{k-j} \right) \approx k $$

and the second term is similar.

Now we've replaced $1_{a<b}$ with a convolution operator. So let's take the discrete Fourier transform:

$$\frac{1}{n}\sum_{0 \leq \xi \leq n-1} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right) \left( \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right)$$

By the Hilbert transform inequality:

$$\left|\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right)\right| \leq \pi k$$

So the bound is

$$\frac{\pi k}{n}\sum_{0 \leq \xi \leq n-1}\left| \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right| \approx \frac{\pi k}{n} \sum_{0 \leq \xi \leq n-1} \frac{n}{2 \pi \min(\xi,n-\xi)} \approx k \log n$$

This gives:

$$k \log n > (1+o(1)) (2r-1) k \log k$$

Hence:

$$n \approx k^{ 2r-1 +o(1) }$$

Here is the matching lower bound:

Suppose that I have two sequences of $k$ numbers, one of which is a sequence of numbers from $1$ to $n_1$ that is increasing with probability $r_1$, and one which is a sequence from $1$ to $n_2$ that is increasing with proobability $r_2$. For any fraction $a/b$, I can construct a sequence of $k^b$ numbers from $1$ to $n_1^a n_2^{b-a}$ that is increasing with probability $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ as follows:

Write a number from $1$ to $k^b$ in base $k$ notation as $b$ numbers from $1$ to $k$. Choose randomly $a$ of the numbers and apply the first sequence, getting a number from $1$ to $n_1$. For the rest, apply the second sequence, getting a number from $1$ to $n_2$. Encode this sequence of numbers lexicographically as a single number from $1$ to $n_1^a n_2^{b-a}$ (generalizing base notation).

For any two numbers $i$ and $j$, consider the first place where they are not equal. In that place, $j$ must be larger than $i$. $d_j$ is equal to $d_i$ in all previous places. Hence as long as $d_j> d_i$ in this place, $d_j>d_i$. The probability that it is greater in this place is at least $r_1$ if this number was chosen and $r_2$ if it wasn't, so the total probability is at least $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$.

This shows that we can take $k=n^{1/f(r)}$ for a convex function $f$. In particular, because we can take $f(1)=1$ (totally deterministic sequence) and $f(1/2-\epsilon)=0$ (totally random), we know $f(r) \leq 2r-1+\epsilon$, so we can get $k$ at least $n^{1/(2r-1)-\epsilon}$

So, obvious question - what is the constant in Terry Tao's bound? It seems to me to be $\pi \log 2 \approx 2.178$. Can this be improved, ideally all the way to $1$?

This strongly suggests that $1/(j-i)$ is in fact the right weight function. Basically, this lower bounding method (and also the previous one) spend an equal amount of work improving the probability that $d_j>d_i$ for $j-i$ at any given scale. So the weight function should make every scale equally valuable, which $1/(j-i)$ does.

(This method is simpler and more general than my previous method.)

Using Fourier analysis in the $d$ variable, we can get the optimal upper bound. As in Tao's argument, if there is a distribution of sequences for which each pair is $r$-probably increasing, there must be a single sequence $d_i$ : such that:

$$\sum_{1\leq a <b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} >(1+ o(1)) (2r-1) k \log k$$

We may rewrite the left hand side as:

$$\sum_{1\leq a ,b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} 1_{a<b}$$

Now use the "carrying the 1" decomposition:

$$ 1_{a<b} = \frac{b}{n} - \frac{a}{n} + \frac{ a-b \operatorname{mod} n}{n}$$

The first two terms are pretty simple. The first term is:

$$\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} \frac{d_j}{n} = \sum_{1 \leq j \leq k} \frac{d_j}{n} \log \left( \frac{j}{k-j} \right) \approx k $$

and the second term is similar.

Now we've replaced $1_{a<b}$ with a convolution operator. So let's take the discrete Fourier transform:

$$\frac{1}{n}\sum_{0 \leq \xi \leq n-1} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right) \left( \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right)$$

By the Hilbert transform inequality:

$$\left|\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right)\right| \leq \pi k$$

So the bound is

$$\frac{\pi k}{n}\sum_{0 \leq \xi \leq n-1}\left| \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right| \approx \frac{\pi k}{n} \sum_{0 \leq \xi \leq n-1} \frac{n}{2 \pi \min(\xi,n-\xi)} \approx k \log n$$

This gives:

$$k \log n > (1+o(1)) (2r-1) k \log k$$

Hence:

$$n > k^{ 2r-1 +o(1) }$$

Note that the base notation trick in the original post allows us to remove the $o(1)$ in the exponent bound by amplification.

Here is the matching lower bound:

Suppose that I have two sequences of $k$ numbers, one of which is a sequence of numbers from $1$ to $n_1$ that is increasing with probability $r_1$, and one which is a sequence from $1$ to $n_2$ that is increasing with proobability $r_2$. For any fraction $a/b$, I can construct a sequence of $k^b$ numbers from $1$ to $n_1^a n_2^{b-a}$ that is increasing with probability $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ as follows:

Write a number from $1$ to $k^b$ in base $k$ notation as $b$ numbers from $1$ to $k$. Choose randomly $a$ of the numbers and apply the first sequence, getting a number from $1$ to $n_1$. For the rest, apply the second sequence, getting a number from $1$ to $n_2$. Encode this sequence of numbers lexicographically as a single number from $1$ to $n_1^a n_2^{b-a}$ (generalizing base notation).

For any two numbers $i$ and $j$, consider the first place where they are not equal. In that place, $j$ must be larger than $i$. $d_j$ is equal to $d_i$ in all previous places. Hence as long as $d_j> d_i$ in this place, $d_j>d_i$. The probability that it is greater in this place is at least $r_1$ if this number was chosen and $r_2$ if it wasn't, so the total probability is at least $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$.

This shows that we can take $k=n^{1/f(r)}$ for a convex function $f$. In particular, because we can take $f(1)=1$ (totally deterministic sequence) and $f(1/2-\epsilon)=0$ (totally random), we know $f(r) \leq 2r-1+\epsilon$, so we can get $k$ at least $n^{1/(2r-1)-\epsilon}$

An explanation of why $1/(j-i)$ is in fact the right weight function. Basically, this lower bounding method spends an equal amount of work improving the probability that $d_j>d_i$ for $j-i$ at any given scale. So the weight function should make every scale equally valuable, which $1/(j-i)$ does.

Suppose that I have two sequences of $k$ numbers, one of which is a sequence of numbers from $1$ to $n_1$ that is increasing with probability $r_1$, and one which is a sequence from $1$ to $n_2$ that is increasing with proobability $r_2$. For any fraction $a/b$, I can construct a sequence of $k^b$ numbers from $1$ to $n_1^a n_2^{b-a}$ that is increasing with probability $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ as follows:

Write a number from $1$ to $k^b$ in base $k$ notation as $b$ numbers from $1$ to $k$. Choose randomly $a$ of the numbers and apply the first sequence, getting a number from $1$ to $n_1$. For the rest, apply the second sequence, getting a number from $1$ to $n_2$. Encode this sequence of numbers lexicographically as a single number from $1$ to $n_1^a n_2^{b-a}$ (generalizing base notation).

For any two numbers $i$ and $j$, consider the first place where they are not equal. In that place, $j$ must be larger than $i$. $d_j$ is equal to $d_i$ in all previous places. Hence as long as $d_j> d_i$ in this place, $d_j>d_i$. The probability that it is greater in this place is at least $r_1$ if this number was chosen and $r_2$ if it wasn't, so the total probability is at least $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$.

This shows that we can take $k=n^{1/f(r)}$ for a convex function $f$. In particular, because we can take $f(1)=1$ (totally deterministic sequence) and $f(1/2-\epsilon)=0$ (totally random), we know $f(r) \leq 2r-1+\epsilon$, so we can get $k$ at least $n^{1/(2r-1)-\epsilon}$

So, obvious question - what is the constant in Terry Tao's bound? It seems to me to be $\pi \log 2 \approx 2.178$. Can this be improved, ideally all the way to $1$?

This strongly suggests that $1/(j-i)$ is in fact the right weight function. Basically, this lower bounding method (and also the previous one) spend an equal amount of work improving the probability that $d_j>d_i$ for $j-i$ at any given scale. So the weight function should make every scale equally valuable, which $1/(j-i)$ does.

(This method is simpler and more general than my previous method.)

Using Fourier analysis in the $d$ variable, we can get the optimal upper bound. As in Tao's argument, if there is a distribution of sequences for which each pair is $r$-probably increasing, there must be a single sequence $d_i$ : such that:

$$\sum_{1\leq a <b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} >(1+ o(1)) (2r-1) k \log k$$

We may rewrite the left hand side as:

$$\sum_{1\leq a ,b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} 1_{a<b}$$

Now use the "carrying the 1" decomposition:

$$ 1_{a<b} = \frac{b}{n} - \frac{a}{n} + \frac{ a-b \mod n}{n}$$

The first two terms are pretty simple. The first term is:

$$\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} \frac{d_j}{n} = \sum_{1 \leq j \leq k} \frac{d_j}{n} \log \left( \frac{j}{k-j} \right) \approx k $$

and the second term is similar.

Now we've replaced $1_{a<b}$ with a convolution operator. So let's take the discrete Fourier transform:

$$\frac{1}{n}\sum_{0 \leq \xi \leq n-1} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right) \left( \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right)$$

By the Hilbert transform inequality:

$$\left|\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right)\right| \leq \pi k$$

So the bound is

$$\frac{\pi k}{n}\sum_{0 \leq \xi \leq n-1}\left| \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right| \approx \frac{\pi k}{n} \sum_{0 \leq \xi \leq n-1} \frac{n}{2 \pi \min(\xi,n-\xi)} \approx k \log n$$

This gives:

$$k \log n > (1+o(1)) (2r-1) k \log k$$

Hence:

$$n \approx k^{ 2r-1 +o(1) }$$

Here is the matching lower bound:

Suppose that I have two sequences of $k$ numbers, one of which is a sequence of numbers from $1$ to $n_1$ that is increasing with probability $r_1$, and one which is a sequence from $1$ to $n_2$ that is increasing with proobability $r_2$. For any fraction $a/b$, I can construct a sequence of $k^b$ numbers from $1$ to $n_1^a n_2^{b-a}$ that is increasing with probability $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ as follows:

Write a number from $1$ to $k^b$ in base $k$ notation as $b$ numbers from $1$ to $k$. Choose randomly $a$ of the numbers and apply the first sequence, getting a number from $1$ to $n_1$. For the rest, apply the second sequence, getting a number from $1$ to $n_2$. Encode this sequence of numbers lexicographically as a single number from $1$ to $n_1^a n_2^{b-a}$ (generalizing base notation).

For any two numbers $i$ and $j$, consider the first place where they are not equal. In that place, $j$ must be larger than $i$. $d_j$ is equal to $d_i$ in all previous places. Hence as long as $d_j> d_i$ in this place, $d_j>d_i$. The probability that it is greater in this place is at least $r_1$ if this number was chosen and $r_2$ if it wasn't, so the total probability is at least $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$.

This shows that we can take $k=n^{1/f(r)}$ for a convex function $f$. In particular, because we can take $f(1)=1$ (totally deterministic sequence) and $f(1/2-\epsilon)=0$ (totally random), we know $f(r) \leq 2r-1+\epsilon$, so we can get $k$ at least $n^{1/(2r-1)-\epsilon}$

So, obvious question - what is the constant in Terry Tao's bound? It seems to me to be $\pi \log 2 \approx 2.178$. Can this be improved, ideally all the way to $1$?

This strongly suggests that $1/(j-i)$ is in fact the right weight function. Basically, this lower bounding method (and also the previous one) spend an equal amount of work improving the probability that $d_j>d_i$ for $j-i$ at any given scale. So the weight function should make every scale equally valuable, which $1/(j-i)$ does.

(This method is simpler and more general than my previous method.)

I think we can do better. I will describe different strategies where the probability that $d_i > d_j$ depends only on $i-j$. Then by choosing a weighted average, we will give a lower bound for this probability greater than $1/2$, despite the fact that the length of the sequence is around $n^2$.

First, if $k \leq mn-m+1$, then we take $d_i = \lceil \frac{i+e}{m} \rceil$ for a random $e \in [0,\dots, m-1]$. Then if $j>i$, the probability that $d_j>d_i$ is $\min ( \frac{j-i}{m},1)$.

To complement it, we want a sequence where the probability that $d_j>d_i$ is close to $1$ for $j-i$ small. We can do the first part by setting $d_i = i+e$ mod $n$ for again a random $n$. However, it declines to $0$ for $j-i$ large, so the best we can get by averaging is $1/2$.

We will do better using more randomization to change the rate of growth. Fix a natural number $l$ and let $\alpha$ be a random real number in $[0,l]$ and $\beta$ a random real number in $[0,n]$. Define $d_i = \lfloor \alpha i + \beta \rfloor$ mod $n$. Then fixing $\alpha$, the probability that $d_j < d_i$

$$f ( \alpha (j-i) \mod n)$$

where $f(x)= (1-1/n) x$ for $x \in [0,1]$ and $1- x/n$ for $x \in [1,n]$.

So the relevant probability is:

$$ \frac{1}{l} \int_0^l f ( \alpha (j-i) \mod n)) d \alpha$$

The probability $\alpha(j-i)$ is in the interval $[0,1]$ modulo $n$, is clearly at most $1/l$. So we may replace $f(x)$ with $1-x/n$ and only lose $1/r$. Another way of writing $1 - \frac{ x \mod n}{n}$ is $1- \operatorname{frac} \left( \frac{x}{n} \right)$

$$ \int_0^l \left( 1- \operatorname{frac}\left(\frac{\alpha (j-i)}{n} \right) \right) d \alpha$$

Using the trivial bound $ \operatorname{frac}(x) \leq x$, this is $\geq 1 - \frac{l}{2}(j-i)$.

It is also easy to see that this is always at least $1/2$. This is because the average value of $1- \frac{x}$ on the whole interval $[0,1]$ is $1/2$, and the largest values come first, so averaging over any subinterval starting at $0$ produces a larger average.

So we have another strategy where the probability that $d_j-d_i$ is at least

$$\max( 1- \frac{l}{2} \frac{j-i}{n}, 1/2) - \frac{1}{l}$$.

Setting $m=n/r$, in our previous strategy the probability was at least:

$$\min( l \frac{j-i}{n}, 1) $$

Choosing a linear combination of $2/3$ this strategy and $1/3$ the previous, we get $2/3 - 2/3l$.

$k$ is proportional to $n^2/l$, hence to $n^2$. Letting $l$ got to $0$, the probability goes to $2/3$. So this shows that for $p=2/3-\epsilon$ we may take $ k \approx n^2$.

This shows that $n^{1/r}$ is not the right upper bound. Most likely this can be improved somewhat.

Suppose that I have two sequences of $k$ numbers, one of which is a sequence of numbers from $1$ to $n_1$ that is increasing with probability $r_1$, and one which is a sequence from $1$ to $n_2$ that is increasing with proobability $r_2$. For any fraction $a/b$, I can construct a sequence of $k^b$ numbers from $1$ to $n_1^a n_2^{b-a}$ that is increasing with probability $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ as follows:

Write a number from $1$ to $k^b$ in base $k$ notation as $b$ numbers from $1$ to $k$. Choose randomly $a$ of the numbers and apply the first sequence, getting a number from $1$ to $n_1$. For the rest, apply the second sequence, getting a number from $1$ to $n_2$. Encode this sequence of numbers lexicographically as a single number from $1$ to $n_1^a n_2^{b-a}$ (generalizing base notation).

For any two numbers $i$ and $j$, consider the first place where they are not equal. In that place, $j$ must be larger than $i$. $d_j$ is equal to $d_i$ in all previous places. Hence as long as $d_j> d_i$ in this place, $d_j>d_i$. The probability that it is greater in this place is at least $r_1$ if this number was chosen and $r_2$ if it wasn't, so the total probability is at least $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$.

This shows that we can take $k=n^{1/f(r)}$ for a convex function $f$. In particular, because we can take $f(1)=1$ (totally deterministic sequence) and $f(1/2-\epsilon)=0$ (totally random), we know $f(r) \leq 2r-1+\epsilon$, so we can get $k$ at least $n^{1/(2r-1)-\epsilon}$

So, obvious question - what is the constant in Terry Tao's bound? It seems to me to be $\pi \log 2 \approx 2.178$. Can this be improved, ideally all the way to $1$?

This strongly suggests that $1/(j-i)$ is in fact the right weight function. Basically, this lower bounding method (and also the previous one) spend an equal amount of work improving the probability that $d_j>d_i$ for $j-i$ at any given scale. So the weight function should make every scale equally valuable, which $1/(j-i)$ does.

(This method is simpler and more general than my previous method.)