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

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 02/11/05 

Date: Fri, 11 Feb 2005 07:26:47 -0600

Well fine then. A few comments on some of your
comments, and then a slight "oops" that I was
going to post even before seeing your reply
(a few times below you say in your defense this
and in your defense that - the "oops" below
seems to me like an excellent "in you defense"
that you missed. Also the oops is very relevant
to my suggestion that all this may be useful
to keep in mind in the future):

On Fri, 11 Feb 2005 09:30:35 +0000, Angus Rodgers
<angus_prune@bigfoot.com> wrote:

>On Thu, 10 Feb 2005 19:40:26 -0600, David C. Ullrich
><ullrich@math.okstate.edu> wrote:
>
>>[...]
>
>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.

I've got no quarrel with calling it a _gap_. A gap
is not the same as an error; not the same as giving
a definition and then writing as though the definition
was different.

>[...]
>>
>>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!

See the "oops" below.

>>[...] 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.

Again, see the "oops" below - it's a much better excuse<g>.

>>[...]

[included just for reference below:]

>>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)).
>>
>>[...]
>
>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?

That's an important part of what I'm saying,
yes. I'm also saying some more substantive
things about O estimates. In my defense, I
said what you say above about taking things
out of context in my first reply (not in those
words) - I also stated Lemma 2 in my first
reply and pointed out that it was correct
and (presumably, depending on exactly what
f was) sufficed to fix the problem.

In your defense:

Oops. I realized this morning that there
are at least two simple proofs of Lemma 2,
and the _simpler_ of the two is the
"wrong" one in terms of what I'm trying to
say. Two proofs:

Proof 1: The hypotheses imply that there
exists M such that f(x) <= Mx for all x > 1. QED.

That's pretty obvious, but if you thought that
that was the proof of Lemma 2 I had in mind then
not realizing I was proposing something totally
different from what you were saying is quite
reasonable - much more reasonable than I
thought you were being at first. Because
Proof 1 simply amounts to saying that one can
use your "reformulation" of things, or it's
pretty close to that, anyway. Proof 1 also
gives you a good excuse for misinterpreting
my use of the word "bounded", etc.

Here's the "right" proof of Lemma 2:

Proof 2: Say f(x) <= Mx for x > x0 and say
f(x) <= c for 1 < x < x0. Then split

  sum_{d<x} f(x/d) = I + II,

where I is the sum of the terms with x/d < x0
and II is the sum of the terms with x/d > x0.
Then (using a standard convention "c denotes
some constant, the value of which may vary
from line to line")

  I <= c x (because there are <= x terms in I)

and

  II <= c x log(x),

QED.

The reason Proof 2 is the "right" one is that it
illustrates a very general paradigm:

GP: "some hypothesis doesn't quite apply to the
whole thing, but the hypothesis applies to the
major part of the whole thing, and the rest of
whatever is easily seen to be negligible in
comparison for some simpler reason."

In particular something like Proof 2 will often
work where something like Proof 1 does not.
(In particular)^2 :

This seems worth mentioning explicitly because
I think you said that you'd noticed that for
some other results in the book your reformulation
didn't suffice to fix the argument! Of course
I can't say for sure, since I have no idea
what these results say, but it seems likely
that something analogous to Lemma 2, either
closely analogous or just loosely analogous,
ie something like GP, will in fact suffice
to fill the gaps in those arguments.

************************

David C. Ullrich

Relevant Pages

  • Re: Removing Spaces in Text Box - Frustrating !
    ... Oops. ... For some reason I didn't see Crystal's reply when I posted. ... If any part of the expression with parentheses is null, ... The info displays....but there is still much more of a gap than just 1 ...
    (microsoft.public.access.reports)
  • Re: sky2 panic in 2.6.32.1 under load (new oops)
    ... Nothing in dmesg.old - have oops in syslog. ... DMAR:[fault reason 05] PTE Write access is not set ... sky2 eth0: disabling interface ...
    (Linux-Kernel)
  • Re: Avengers Invaders MU
    ... Come on name one reason. ... possibly written that could "even" remotely justify calling me a dick. ... It's that you make a point of saying "Oops, ... Personally, I tend to read spoilers, but many ...
    (rec.arts.comics.marvel.universe)
  • Re: Look out below!!!
    ... Oops. ... I guess you'll have to come up with another insult. ... I'm waiting for you to tell me what else you could possibly have meant. ... tell me I was wrong, but when countered with reason and evidence, that you ...
    (alt.fan.howard-stern)
  • Re: What is this about - VMS advertising ?
    ... They really seem to push the defense side ... There are two Windows Media Files ... Oops. ...
    (comp.os.vms)