Re: Problem with `big oh' estimates in number theory

From: Angus Rodgers (angus_prune_at_bigfoot.com)
Date: 02/09/05 

Date: Wed, 09 Feb 2005 16:27:16 +0000

On Wed, 09 Feb 2005 08:39:08 -0600, David C. Ullrich
<ullrich@math.okstate.edu> wrote:

>On Wed, 09 Feb 2005 13:16:00 +0000, Angus Rodgers
><angus_prune@bigfoot.com> wrote:
>
>what seems most likely
>to me is that you're overlooking facts that he's using
>without stating explicitly because he thought they
>were obvious.

No, he's using the fact that certain terms, which are
functions of the number q = x/d, are bounded for *all*
values of q >= 1, and not just for all `sufficiently
large' values of q. The lower bound for `sufficiently
large' *has* to be 1, for these proofs to work at all.

My point is that this fact is essential to all three
of his proofs, but it has never been stated by him.

This isn't just some `obvious' point, which he expects
the mathematically mature reader to work out for him/
herself. If that were the case, then filling in the
missing steps of the argument would not have required
a strengthening of the conclusion of a preceding theorem!

>>The proof of Theorem 3.4 contains this deduction, for x >= 1:
>>
>
>
>[*]
>> sum_{d <= x} ((1/2)(x/d)^2 + O(x/d))
>> = (x^2/2)*(sum_{d <= x} 1/d^2) + O(x*(sum_{d <= x} 1/d))
>>
>>Of course there is no doubt that sum_{d <= x} (1/2)(x/d)^2
>>= (x^2/2)*(sum_{d <= x} 1/d^2), so Apostol's statement is
>>logically equivalent to the proposition:
>>
>> sum_{d <= x} O(x/d) = O(x*(sum_{d <= x} 1/d)) = O(x*log(x))
>>
>>But this is false. For a counterexample, define a function f:
>>[1, oo) --> R by f(1) = 0 and f(q) = q^3/(q - 1)^2 for q > 1.
>>Then |f(q)| <= 4q for q >= 2, therefore f(q) = O(q). But:
>>
>> sum_{d <= x} f(x/d)
>>[...]
>> ~ zeta(2)x^2
>>
>>which is not O(x*log(x)).
>
>Well, [*] is not a deduction, it's an equation.

I hesitated over what word to use, and `deduction' may not
have been a fortunate choice; but `equation' is definitely
wrong, and I rejected it quite deliberately. A relation/
statement/proposition/assertion/*whatever*, of the form
A + O(g) = B + O(g), is not an equation. For one thing,
it isn't a symmetric relation, e.g. we have O(1) = O(x),
but not O(x) = O(1).

However, let's not argue about a merely semantic problem
like this - please! (At least not until the main point
has been settled - there already seems to be enough scope
for misunderstanding there! Much to my surprise, I must
say, but then this whole thing is surprising to me.)

>Seriously - it seems unlikely that [*] appears
>alone, surely what's in the book is
>
> F(x) = sum_{d <= x} ((1/2)(x/d)^2 + O(x/d))
>
> = (x^2/2)*(sum_{d <= x} 1/d^2) + O(x*(sum_{d <= x} 1/d))
>
>for some function F,

Yes.

>and the deduction involved is
>"F(x) = sum_{d <= x} ((1/2)(x/d)^2 + O(x/d)),
>hence F(x) = (x^2/2)*(sum_{d <= x} 1/d^2) + O(x*(sum_{d <= x} 1/d))".
>That deduction could be valid in spite of your counterexample
>to [*], because of extra facts not stated.

No, the /deduction/ cannot be /valid/!* Its /conclusion/
is /true/ - true, indeed, because of extra facts not stated,
to which I have myself drawn attention! But, as we both
know very well, that's quite a different matter, and I'm
quite surprised to see you argue in this way. Perhaps
I'm missing your point (although it seems unambiguous).

My point is that the statements here of the form "A + O(foo)
= B + O(bar)" *do not prove anything*. There is no way of
interpreting them that makes them valid as, er, deductions.

*Modulo some ***-up on my part, of course.

>For example, the f in your counterexample is rather badly
>unbounded near q = 1. It's not hard to show that if f is
>bounded on (0,x_0] and |f(x)| <= Mx for x > x_0 then
>sum_{d <= x} f(x/d) = O(x*log(x)). So the question would
>be whether the function giving the error term is clearly
>bounded on (0,x_0) in the proof that
>F(x) = sum_{d <= x} ((1/2)(x/d)^2 + O(x/d));
>[...]

It is indeed bounded, but it is not *clearly* bounded,
and that is my whole point. The proof that the terms
in question (in the three proofs) are bounded for all
values of the argument >= 1 is *exactly* the same as
the proof given by Apostol that they are O(foobar).

The point is that you *need* the fact that the lower
bound of the argument for the O()-inequality to apply
is 1, in each of the four cases considered (in Theorem
3.2), but, by using the O() notation, he throws this
vital information away, even though, apparently without
realising it, he needs it immediately, in the proofs of
Theorems 3.4, 3.5 and 3.7.

>Couldn't say without seeing exactly what's in the book.

Well ... !

>For example you say he gives preliminary results on
>zeta(s), of the form
>
> zeta(s) = main terms + O(error terms).
>
>Do the main terms there blow up like 1/(s-1) as s decreases to 1?

No, but again, this is exactly my point! It isn't
*obvious* that they don't blow up near 1; it needs
to be *stated*. Representing the behaviour using
the O() notation throws away vital information.

(I'm aware that I've repeated myself several times
here, and I'm sorry; but I'm getting frustrated
trying to get my point across, and I don't know
how many other ways there are to say it! I hope
I haven't just muddied the waters further.) 

-- 
Angus Rodgers
(angus_prune@ eats spam; reply to angusrod@)
Contains mild peril