Talk:Sorting number

Errors in the article

The inequality A(n) ≤ n log2 n - .915 n is false for n from 1 to 30, from 37 to 52, from 70 to 100, and so on ... For some n's, the said inequality is true and for infinitely many others, it is false.

To begin with, it is false for all A(n)'s listed in the article (the first 14 sorting numbers):

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41.

It is easy to compute with a calculator the values of n log2 n - .915 n for n = 1 ... 14. here are these values:

-0.915, 0.17, 2.00989, 4.34, 7.03464, 10.0198, 13.2465, 16.68, 20.2943, 24.0693, 27.9887, 32.0396, 36.2107, 40.493

One can see that all these values are less than the corresponding sorting numbers A(n).

And it gets worse and worse for selected larger and larger n.

For instance, for n = 22,000

A(n) = 297,233 while n log2 n - .915 n = 297,224.74987258646

for n = 44,500

A(n) = 646,465 while n log2 n - .915 n = 646,430.0383454675

for n = 89,000

A(n) = 1,381,929 while n log2 n - .915 n = 1,381,860.076690935

for n = 178,000

A(n) = 2,941,857 while n log2 n - .915 n = 2,941,720.15338187

and so on.

As a matter of fact (proved in plain and simple), it follows that the upper limit of the difference A(n) - (n log2 n - .915 n) must diverge to ∞ with n. Which makes the following sentence from the article false:

"Asymptotically, the value of the $n$th sorting number fluctuates between $n\log _{2}n-n$ and $n\log _{2}n-0.915n$ depending on the ratio between $n$ and the nearest power of two."

I corrected it to:

"The value of the $n$th sorting number fluctuates between $n\log _{2}n-n+1$ and $n\log _{2}n-0.913n+1$ depending on the ratio between $n$ and the nearest power of two."

and provided a reference to it, but an individual using Wikipedia user name MrOllie reversed my correction, restored false inequality, and falsely referenced it to an article that didn't even mention that inequality.

I can't know what his intentions are but if he wants Wikipedia to lose whatever is left of its credibility then that's the way to go. M A Suchenek (talk) 21:41, 2 June 2021 (UTC)

It's right there on page 3 of the Ford article. Also, as I have explained to you elsewhere, Wikipedia cannot use your arxiv preprint as a source. If Ford and Johnson got it wrong we can remove it, but we cannot substitute your original research. Ford and Johnson do note that their decimal value are approximations, though, and the initial author of our Wikipedia article did not do that. I've just added that. - MrOllie (talk) 11:02, 3 June 2021 (UTC)

No, it is not. That reference (p. 3) only states - with no proof whatsoever - that (here, M(n) in the reference has the same meaning as A(n) in the article):

$M(n)$ ~ $n\log _{2}n-0.915n+\Theta (\log _{2}n)$,

which just means that:

${\frac {M(n)-(n\log _{2}n-0.915n+\Theta (\log _{2}n))}{n\log _{2}n-0.915n+\Theta (\log _{2}n)}}$ → 0.

Although the above is true, but so is:

${\frac {M(n)-(n\log _{2}n-1,000n+\Theta (\log _{2}n))}{n\log _{2}n-1,000n+\Theta (\log _{2}n)}}$ → 0

simply because ${\frac {n+c\log _{2}n}{n\log _{2}n}}$ → 0.

An interpretation of the above as

$M(n)-(n\log _{2}n-0.915n)\in \Theta (\log _{2}n)$

or as M(n) ≤ n log2 n - .915 n for n larger than certain n0 (as it was done in the article), is false, as I indicated, previously.

The smallest c for which the inequality M(n) ≤ n log2 n - c × n + 1 holds is

$c=1-\delta$

where δ is the Erdos constant approx. equal to 0.0860713320559342. See for proof of it, and for a graph (on Fig. 4 in ) of both sides of the said inequality that visualizes asymptotic approximation of the upper bound RHS of A(n) by the LHS as n → ∞. M A Suchenek (talk) 20:16, 8 June 2021 (UTC)

References