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

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

Date: Fri, 11 Feb 2005 09:30:35 +0000

On Thu, 10 Feb 2005 19:40:26 -0600, David C. Ullrich
<ullrich@math.okstate.edu> wrote:

>On Thu, 10 Feb 2005 16:55:48 +0000, Angus Rodgers
><angus_prune@bigfoot.com> wrote:
>
>>On Thu, 10 Feb 2005 07:24:55 -0600, David C. Ullrich
>><ullrich@math.okstate.edu> wrote:
>>
>>>On Wed, 09 Feb 2005 16:27:16 +0000, Angus Rodgers
>>><angus_prune@bigfoot.com> wrote:
>>>
>>>[...]
>
>>Satisfied yet?
>
>Maybe you should try to relax a little.

I wouldn't know how to try to relax! However, the
fact that (thanks to what follows) I've finally got
your point - and have finally seen that you had got
my point all along - has a relaxing effect.

(I still feel altogether too much like JSH, though.
Funny farm, here I come!)

>I believe that
>you're wrong about something here. You've pointed out
>several times you could be wrong about various
>things that you're not in fact wrong about, but the one
>thing that it seems to me that you _are_ wrong about
>you're simply dismissing by assertion. (see below).

It should be amusing, as well as embarrassing, for me
to re-read my various long and increasingly agitated
posts, to see exactly where and how I was missing the
point of what you were saying. But I don't think that
I'll be posting at length about it!

>Believe it or not the reason I'm continuing to insist
>that I think you're wrong about something is that
>I do think you're wrong about it, and you say you're
>trying to learn this stuff - if I'm not wrong then
>you'd be better off if you got this error straight,
>because it's the sort of thing that will come up
>again.

I'm not sure that I exactly made an "error". (Got to
salvage some dignity here!) Apostol's book is written
for beginners in the subject, and nowhere else (so far)
does he leave such a gap in the argument.

I do understand now that if the proof had occurred in
a paper written for professionals, the gap would not
excite any comment, and indeed would not be regarded
as a gap.

But I can also still put myself in my former frame of
mind, and see that it really did look as if that step
of the argument was intended to be entirely justified
by whatever definition was in force for O(), and that
definition could not be the one with variable x_0.

>>Apostol didn't /intend/ the reader (whether "mature"
>>or not) to fill in the gap. It was a /mistake/!
>
>Could be. But I've read what you've said about all
>this, and I'm not convinced.

Neither am I, now. (A mistake in level of exposition,
perhaps, but nothing more.)

>>When an author expects a reader to fill something
>>in, he does not expect the reader to reformulate
>>a result which has already been stated, proved,
>>and appealed to - which is what I had to do here.
>
>Reformulating things has nothing to do with
>what I think the problem is.

Well, it did look like it, that's all I can say!

>Lemme try again. Try to read the following with
>an open mind.

"The trouble with having an open mind is that
people come along and put things in it."

>You say you're frustrated at your
>inability to get your point across. For a few minutes
>try to consider the possiblility that you _have_
>got your point across, but that your point is
>simply wrong because of something you're
>misunderstanding.
>
>Do read it all once. I know that you _have_
>misunderstood various things I've said - I
>know because of one spot where you agree you
>simply misread something, another place where
>I say "bounded" and you explain that of course
>bounded was not exactly what I meant, when in
>fact it _was_ exactly what I meant.

My excuse for that is that last misunderstanding
is that I was under extreme time pressure. (I'm
about 4 days behind with lots of stuff now.)

>Etc. So:
>
>Consider Lemma 1:
>
>Lemma 1: If f(x) = O(x) then
>
> sum_{d<x} f(x/d) = O(x log(x)).
>
>Now Lemma 1 is indeed wrong, as you point out.
>If he'd stated Lemma 1 explicitly that would
>be an error. But I gather he didn't. If he'd
>_used_ Lemma 1 that would be an error - at the
>very least an error in giving one definition
>of O and then using O as though he'd given a
>different definition, which is what you think
>happened, or so I gather from your comments
>about x_0=1 - this has nothing to do with
>what I think is going on: I'm not convinced
>from anything you've said that he _did_ use
>Lemma 1 - I think that you're simply misunderstanding
>the argument (which is why I'm giving this
>explanation one more try, to help you understand
>similar arguments in the future).
>
>The reason you believe he's using Lemma 1 is
>that you see something written of the form
>
>[*] something = whatever + sum_{d<x} O(x/d)
> = whatever + O(x log(x)).
>
>In your OP you said (more or less) that the
>fact that he wrote [*] shows that he's
>using Lemma 1. I said in my first reply
>that this didn't follow, and you simply said
>no, writing [*] _does_ show that he's using
>Lemma 1.

In my defence, at this exact point in my reply
to your reply, I also wrote:

 Perhaps I'm missing your point (although it
 seems unambiguous).

and:

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

You had just written:

>That deduction could be valid in spite of your
>counterexample to [*], because of extra facts
>not stated.

which only says "could be", and doesn't mention
/which/ "extra facts" you had in mind.

As: (1) you didn't have a copy of the book to hand,
and (2) I had myself mentioned extra facts needed
to complete the deduction, I think it was quite
natural for me to conclude that you could only be
referring to these facts, and had somehow missed
my point.

But in fact, you hadn't.

Can I at least convict you of a "mistake in
exposition" at this point? :)

>And although you mentioned
>This is exactly what I think you're
>misunderstanding - when an author writes
>[*] it simply does not follow that he's
>using the erroneous Lemma 1.

That's clear now, thanks. (But see my
qualification at the end of this post.)

>Consider Lemma 2:
>
>Lemma 2: If f is bounded on every interval
>of the form (1,x_0) (with a different bound
>for each x_0) and f(x) = O(x) then
>
> sum_{d<x} f(x/d) = O(x log(x)).
>
>Now, Lemma 2 is _true_. It's very easy to prove,
>and whether you agree that it's sufficiently
>trivial to make this appropriate or not, it
>_is_ the sort of thing that people writing
>for a mature audience will often use,
>without _mentioning_ the fact they're using,
>much less proving it.

I shall frame this! :)

>Suppose I wrote
>
>[i]
>
>"Since f(x) = O(x), Lemma 1 shows that
>
> sum_{d<x} f(x/d) = O(x log(x))."
>
>That would be an error, since Lemma 1 is false.
>
>Suppose that I'd never said anything about
>the fact that f was bounded on (1,x_0) for
>every x_0, and I wrote
>
>[ii]
>
>"Since f(x) = O(x), Lemma 2 shows that
>
> sum_{d<x} f(x/d) = O(x log(x))."
>
>If f was in fact bounded on (1,x_0) for
>every x_0 that would not be an error, it
>would be a missing detail - whether it would
>be appropriate to leave that detail out
>would depend on how obvious it was that f
>was bounded on every (1,x_0). But if f actually
>_is_ bounded on every (1,x_0) then [ii] is
>_not_ an error.
>
>Now suppose I read
>
>[iii]
>
>"Since f(x) = O(x)
>
> sum_{d<x} f(x/d) = O(x log(x))."
>
>I might at first assume that the author
>was applying Lemma 1. If I noticed that
>Lemma 1 was false I might at first assume
>that this was an error - with any luck I'd
>realize that Lemma 2 was true, and if the
>author seemed to know what he was doing
>I would then assume that he was actually
>applying Lemma 2.
>
>Really. [ii] is _not_ an error, it's just
>a missing detail. And since [iii] is exactly
>the same as [ii] with a few words deleted it
>follows that [iii] is not necessarily an error
>either, it could be just a missing detail.
>
>Unless I'm totally misunderstanding the whole
>thing, it's as though he'd written [iii] and
>you're convinced that he _must_ have meant [i],
>which is wrong.

Actually, you are still misunderstanding something
here. (Hooray!)

What's missing from your otherwise admirably clear
account is any recognition of the fact, which I
have so often repeated, that there is also (so to
speak) /another/ unwritten lemma:

Lemma 1': If f(x) = O(x) then

  sum_{d<x} f(x/d) = O(x log(x)).
.
"Hang on a minute!" you cry, "That's just my
Lemma 1 again! What are you trying to pull?"

My point is that your Lemmas 1 and 2 are /not/
the only "extra facts" to which Apostol could
have been alluding. It was entirely possible
(but now I agree that it is probably not true)
that he might have had in mind, when proving
his theorems, a different definition of O()
than the one he had explicitly stated.

That was what I thought had happened. I did
not imagine that he ever consciously thought
that /your/ Lemma 1 was true! That would be
silly, and I'm not silly enough to imagine
that Apostol is that silly! I just thought
that he knew perfectly well that /my/ Lemma
1' /is/ true.

Apostol might have unconsciously equivocated
in his definition of O() - and still "known
what he was doing" in a more important sense.

But, re-reading my original post, I can see
that I didn't make it at all clear that this
was what I meant. I wrote:

 Apostol appears to assume generally that for any function g
 which is eventually positive:
   sum_{d <= x} O(g(x/d)) = O(sum_{d <= x} g(x/d))

And:

 The only way I can see to fix the problem is to change the
 local definition of O() to the one with fixed value x_0 = 1.

I thought Apostol was /using/ this definition,
without having /stated/ it. Also: his theorems
up to this point were true using this definition;
/and/ the three proofs that puzzled me all became
perfectly transparent on the assumption that
this definition of O() was what Apostol /really/
had in mind (in spite of having explicitly
stated something else).

But you responded accurately to what I wrote,
which wasn't exactly what I meant to say. My
fault, still, I suppose. But I wasn't being
quite so JSH-like as you seem to have supposed!

(I feel better now. The curse of JSH is lifted!)

>I don't see how you can be so
>certain that [ii] is not what he had in mind,
>in which case there's nothing erroneous about it.

I'm pretty much convinced now that this is what
he had in mind, and he did intend O() to be used
exactly as he had defined it - not with a fixed
x_0 = 1.

I'm not /totally/ sure, but I'll keep on mulling
this over.

>**********************
>
>Ok, above I've changed the syntax a good deal.
>You say he actually wrote [*]. But any time
>you see something like [*] you have to realize
>that there's a bit of informality, for example
>the author _must_ have one fixed error term
>f(x/d) in mind when he wrote O(x/d) inside that
>sum, because if the O(x/d) could refer to
>different x_0 and different constant M for each
>value of d then [*] makes no sense at all.
>But if we assume as we must that all those
>O(x/d)'s are referring to the same function
>then [*] looks to me just like [iii].

I've read this bit several times, but still can't
see what you are getting at. Certainly all the
O(x/d)'s must be understood to refer to the same
function f(x/d). That was never in question.

I think a little light is beginning to dawn.

If I had seen your [iii], in an argument in
Apostol's book or anywhere else, I might well
have been more open-minded in my guess as to
what "extra facts" the author had in mind; and
I might even have come up with your Lemma 2,
instead of "my" version of Lemma 1 (which I
mischievously called Lemma 1').

But instead, what I saw was an equation-like
statement [*], which looked for all the world
as if it were intended to be capable of being
taken out of context. But if you do take this
one line of the proof out of context, then it
becomes false, unless the definition of O() is
changed (in a quite reasonable-looking way).
There are no other alternatives. That much
of what I wrote is (I still think) correct.

So perhaps what, essentially, you are telling
me is that a single line of a proof like this
cannot always validly be taken out of context,
and I should be alert to this possibility in
more advanced expositions of mathematics? 

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