3
$\begingroup$

The relations ~ and ≍ are frequently used in math and computer science, at least within number theory and analysis of algorithms. What is their origin?

Definitions

Suppose $g(x)$ is an eventually-positive function of $x$. Then

$$ f(x) \sim g(x) $$

if and only if

$$ \lim_{x\to\infty} f(x)/g(x) = k $$ with $0<k<\infty,$ while

$$ f(x) \asymp g(x) $$ if and only if $$ 0 < \liminf_{x\to\infty} f(x)/g(x) \le \limsup_{x\to\infty} f(x)/g(x) < \infty. $$

Note that the defintion of ~ replaces the $\le$ for $=$ in the above.

Related work

I believe the related notations $\ll$ and $\gg$ are due to Vinogradov, while $O/o/\Omega/\omega$ are due to Hardy and Littlewood. (I've skimmed through Hardy's Orders of Infinity which suggests that he and Paul Du Bois-Reymond did some early work here but I don't think that either of these notations originated there.)

I was not able to find these in either of these online resources:

$\endgroup$

1 Answer 1

4
$\begingroup$

The notation $\sim$ does not mean that ratio $f(x)/g(x)$ has some positive limit $k$, but that it has limit $1$, e.g., $2x + \sqrt{x} \sim 2x$. What math books do you know that define $\sim$ in the way you did? It would allow us to write $2x+\sqrt{x} \sim x$, which is a meaning of $\sim$ that I've never seen.

This notation $\sim$ is due to Landau: see page 62 of the first volume of his Handbuch der Lehre von der Verteilung der Primzahlen (1909). It's available at archive.org here.

The $O$-notation and $o$-notation are not due to Hardy and Littlewood:

  1. The $o$-notation is due to Landau in the same book I already mentioned, on page 61.

  2. The $O$-notation is due to Bachmann on p. 401 of his book Die Analytische Zahlentheorie (1894) here.

$\endgroup$
1
  • $\begingroup$ Probably $\Omega$ and $\omega$ are more recent than Hardy and Littlewood. $\endgroup$ Jul 16, 2023 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.