Re: Problem with `big oh' estimates in number theory
From: Angus Rodgers (angus_prune_at_bigfoot.com)
Date: 02/11/05
- Next message: Lester Zick: "Re: Epistemology 201: The Science of Science"
- Previous message: aeo6: "Re: Epistemology 201: The Science of Science"
- In reply to: David C. Ullrich: "Re: Problem with `big oh' estimates in number theory"
- Next in thread: Randy Poe: "Re: Problem with `big oh' estimates in number theory"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 11 Feb 2005 15:17:47 +0000
On Fri, 11 Feb 2005 07:26:47 -0600, David C. Ullrich
<ullrich@math.okstate.edu> wrote:
>[...] 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)
Yes, you did; but even now, I had to read the
message twice, before realising that that was
what you were saying. It needed more emphasis
if it was ever going to penetrate my skull!
>- 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.
That's more or less what happened. But it leaves
out a rather important part of the story, which I
didn't even bother to tell (not realising that it
would ever be important):
>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 :
In another post in this thread, I wrote something
about rough scribbles turning out often to be
useful for much longer than I anticipated at the
time of writing them!
Imagine, then, that you have in front of you, not
only a copy of Apostol's book, but also a copy of
my rough notebook, opened to the pages for Friday
4 February, which is when I ran into this problem.
You will see there that your Proof 2 is the very
first thing I wrote down in attempt to solve the
difficulty!
I didn't carry it through to the end, though.
Rather, I wrote down ...
Hmm, in fact, the reason I didn't carry it through
is that it appeared to be (although with /infinite/
hindsight it can be seen not to be!) too weak to
solve the general case.
It only works easily in this one case, g(q) = q, on
which you have concentrated. But I needed it more
generally, for instance when g(q) = q^alpha for some
arbitrary alpha > 0.
Apostol's proof of Theorem 3.5 (where the case alpha
= 1 is excluded) proceeds by replacing (sum_{d <= x}
O(x^alpha/d^alpha)) by O((x^alpha)(sum_{d <= x}d^alpha)),
and then showing that this term is O(x^beta), where
beta = max{1, alpha}. It actually consists of three
parts, which are respectively O(x), O(x^alpha), and
O(1).
The sum `I' in your Proof 2 would give another O(x)
term, which would be absorbed, leading to the same
result as Apostol gets. Fine! But no such extra O(x)
term appears in Apostol's proof.* All three terms
are immediately derived from his Theorem 3.2 (b)
(as he explicitly says, even if it weren't obvious).
*(I really wish I could underline this sentence, or
put it in italics, or something. _..._ and /.../
just aren't emphatic enough.)
He gets to O(x^beta) via O((x^alpha)(sum_{d <= x}d^alpha)).
/If/ he had had your Proof 2 in mind, he /would/ have got
to O(x^beta) via O((x^alpha)(sum_{d <= x}d^alpha)) + O(x).
Therefore /he could not possibly have had your Proof 2
in mind/. (Or else he amazingly forgot to actually write
down any evidence of it, in any of the many proofs where,
if you were right, he must have been thinking of it; but
this defies belief.)
Let me try and make this clearer. (I'm incredibly
pushed for time, and tried to finish that all in a
rush, but it came out more convoluted than it need
have been.)
In his proof, he writes down O((x^alpha)(sum_{d <= x}d^alpha))
/before he even knows/ that it is the correct error term!
(That is, according to your theory that he has Proof 2
in mind.) Only later does he write down the expression
for this sum (using Theorem 3.2 (b)) which makes it
clear that the O(x) term corresponding to your sum
`I' will be absorbed into the whole. That is on the
next line of the proof. The sequence of the deduction
is all wrong, for your account of it to make sense.
Was that any clearer? I hope so. I've got to dash.
Damn, haven't quite finished yet:
Anyway, rather than attempt to estimate your sum `I',
I wrote, "Actually, we can circumvent this difficulty
if ...", and went on to develop my theory that Apostol
really had x_0 = 1 in mind.
So I'm afraid you've got the cart before the horse.
>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.
I don't think I said anything like that. Maybe
it was something Paul Pollack said about a
theorem in a later chapter that I haven't got
to yet?
-- Angus Rodgers (angus_prune@ eats spam; reply to angusrod@) Contains mild peril
- Next message: Lester Zick: "Re: Epistemology 201: The Science of Science"
- Previous message: aeo6: "Re: Epistemology 201: The Science of Science"
- In reply to: David C. Ullrich: "Re: Problem with `big oh' estimates in number theory"
- Next in thread: Randy Poe: "Re: Problem with `big oh' estimates in number theory"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
