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

From: Randy Poe (poespam-trap_at_yahoo.com)
Date: 02/11/05 

Date: 11 Feb 2005 06:45:34 -0800

Angus Rodgers wrote:
> >Are you saying that x is a constant, and so is d? So what
> >formally does O(x/d) mean here? What's the free variable?
>
> I'm sorry (really!), but I (still) don't know exactly
> what you mean!
>
> I think of O(x/d) here as an expression - or rather,
> /almost/ as an expression - in exactly the same way
> as zeta(2) is an expression.

zeta(2) is a number.

For me f(x) = O(g(x)) means that you can draw two
graphs, one of f(x) and one of M*g(x) for some M,
and the graph of f(x) lies entirely under the graph of
M*g(x). There's definitely more than one number involved
here, it's a statement about the behavior of an entire
function over a range which is unbounded to the right.

So when I say "the free variable" I mean the horizontal
axis of that graph.

When I see f(x) = O(x/d) I mean that I am plotting
f(x) vs. x. I mean that I am also plotting the straight
line Mx/d which goes through the origin and has slope M/d.
And I see that f(x), while it may cross above that line
for small x, eventually lies entirely under it for x
large enough.

> Certainly `x/d' is an
> expression. There isn't anything here that I would
> think of a "free variable".* In the context of the
> proof in Apostol's book, the variables x and d are
> bound* to values; so, therefore, is x/d; and so - in a
> rather vague sense, which I won't attempt to expound
> (because I'd screw up, being pushed for time, and, as
> I keep saying /ad nauseam/, tired!) - so is `O(x/d)'.

Well, when you complete the statement, applying the
definition of O(x/d), at some point you are going to
say "for all [***] >= [...]". So I'm saying the the
free variable is the thing for which you are considering
all values above [...]. In other words, it's what you
are putting inside [***].

> >I assumed x was the free variable, and g(x) = x/d for
> >a particular value of d. d is a parameter in g(x).
>
> No, I think that's wrong, unless (still quite likely)
> I'm misunderstanding your meaning. There's just one
> function g(x) here ... but better call it "g(q)", to
> avoid (still more) confusion.

And yet when you write f(x) = O(g(x)) the x inside
the expression is the same x as in f(x). You must have
the ability to plot both on the same set of axes.

> In fact, if I'm not
> (I probably am*) mistaken, it's:
>
> g(q) = (sum_{n <= q} n) - (q^2)/2

I don't know why you're introducing a sum here. I
might be willing to believe Apostol is using some
strange meaning of O(g(x)) which I haven't seen before
and which involves a sum, but I don't think so since
you've stated explicitly the same definition I'm used
to. And for that definition, O(x/d) means you plot x/d
vs. x, and compare it to f(x) vs. x. I'm still waiting
for higher authority here. Apologies for snipping the
rest of this.

HOWEVER... having said all that, it would be a strange
thing to write O(x/d), since it is identical to
O(2x) or O(3x) or O(x). So there is SOMETHING unusual
about the way Apostol is using it, and perhaps it is
that he is implying from the start that all the
f_d(x) are uniformly bounded by the same Mx/d.

              - Randy

Relevant Pages

  • Re: summing x-y data files using matlab
    ... I have about a 100 x-y data files, and I'd like to sum them up to one x-y ... graph. ... If you're looking to actually add up the data, interpolate the data ...
    (comp.soft-sys.matlab)
  • Re: Graph problem, is it NP-Complete?
    ... The graph has always a "line-like" structure, ... where each subsequence can only contain a particular unique value. ... If an interior value is greater than the sum of its neighbours, ...
    (comp.theory)
  • Re: Some Paradox on Confidence Interval of Population Parameter!
    ... Yi = Xi/N ... GRAPH 1 ... Rate of Change of Sum Yi ... Since Yi is the population parameter for day i, ...
    (sci.math)
  • Re: Generate a sound: freq / amplitude ??
    ... generate a sum of sines according to a graph: ... is how additive synthesis works (an arbitrary waveform being the ... sum of a possibly infinite number of sinusoidal waveforms). ... Vocatus atque non vocatus deus aderit ...
    (rec.music.makers.synth)
  • Re: 3-Coloring given the adjacency matrix?
    ... "Apostol" wrote in message... ... Does anybody know where can I find a function that colors a graph with 3 colors? ... e.g. given an adjacency matrix the output would be a vector saying which node belongs to which group/color? ...
    (comp.soft-sys.matlab)