MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 4 characters in body

This is a comment on gowers' answer, but it is long enough that I am making it an answer on its own.

I don't think this quite works. If $[a_0, a_1, \ldots, a_i]=p_i/q_i$, and $x$ is the value of the infinite continued fraction, then $$|x-p_i/q_i|= 1/(q_i q_{i+1})-1/(q_{i+1} q_{i+2}) + \cdots \approx 1/(q_i q_{i+1}).$$ We have $a_{i+1} q_i < q_{i+1} < (a_{i+1} +1 ) q_i$, so $q_{i+1} \approx a_{i+1} q_i$.

If $a_i$ is a permutation of the integers which doesn't reorder them too much then $a_i$ is about $i$ so $q_i \approx i!$. Inverting Stirling's approximation, $i \approx \log q_i/\log \log q_i$.

So we have $$|x-p/q| \approx \frac{\log \log q}{q^2 \log q}.$$

This is consistent with Roth's theorem.

My hazy memory is that there is a conjecture that, for $\phi(q)$ a decreasing positive function, there is an algebraic number $x$ with infinitely many solutions to $|x-p/q| < \phi(q)$ if and only if $\sum q \phi(q)$ diverges. That would predict that the error rate above is consistent with being algebraic. Does any one know if I remember this correctly?

1

This is a comment on gowers' answer, but it is long enough that I am making it an answer on its own.

I don't think this quite works. If $[a_0, a_1, \ldots, a_i]=p_i/q_i$, and $x$ is the value of the infinite continued fraction, then $$|x-p_i/q_i|= 1/(q_i q_{i+1})-1/(q_{i+1} q_{i+2}) + \cdots \approx 1/(q_i q_{i+1}).$$ We have $a_{i+1} q_i < q_{i+1} < (a_{i+1} +1 ) q_i$, so $q_{i+1} \approx a_{i+1} q_i$.

If $a_i$ is a permutation of the integers which doesn't reorder them too much then $a_i$ is about $i$ so $q_i \approx i!$. Inverting Stirling's approximation, $i \approx \log q_i/\log \log q_i$.

So we have $$|x-p/q| \approx \frac{\log \log q}{q^2 \log q}.$$

This is consistent with Roth's theorem.

My hazy memory is that there is a conjecture that, for $\phi(q)$ a decreasing positive function, there is an algebraic number $x$ with infinitely many solutions to $|x-p/q| < \phi(q)$ if and only if $\sum q \phi(q)$ diverges. That would predict that the error rate above is consistent with being algebraic. Does any know if I remember this correctly?