Talk:L-notation

Flawed example?

In the main part of the article, we say α=1 gives a "fully exponential" function. However, in the example, α is 1, yet we say the function is $n^{\frac {1}{2}}$. If these statements are both right (which I doubt), they are certainly confusing. --Doradus 16:05, 30 August 2007 (UTC)

The article's right. $n^{\frac {1}{2}}$ is exponential in ln n although it's just polynomial in n.

CRGreathouse (t | c) 19:52, 18 October 2007 (UTC)

More info needed so this is not a stub

We currently have a basic definition, plus a rather unhelpful example. Can anyone provide:

• History: who introduced this notation? Who uses it now?
• Significance: why/when is this used instead of big O notation?
• An example where α is not zero or one?

Thanks. --Doradus (talk) 14:58, 27 December 2008 (UTC)

Tentatively, I would say that the L is named for (and possibly also by) some person named L. Topping the list would be candidates like Landau, Lehmer and Lenstra. For example, a bit of follow-the-footnotes suggests that H. Lenstra may have invented the notation:

"At this point we need an unproved conjecture. For a real number χ > e, define

$L(x)=e^{\sqrt {\log x\log \log x}}$"

- H. W. Lenstra, Jr., "Factoring integers with elliptic curves", Annals of Mathematics vol. 126 pp. 670, 1987.

The peculiar mouthful that a simple $L(\alpha ,c)$ expands to in big-O seems to have something to do with the distribution of prime numbers . The algorithms measured by L-notation involve small prime numbers (for factor bases and group orders and what-not), so L-notation might be a good way to filter out the statistical variation for similarly-sized inputs , which big-O is too fine-grained for.

The Encyclopedia of Cryptography and Security entry on "L-notation", pp.358, could be a useful source in general [1]. ~ Jafet•work•play•watch 17:51, 27 December 2008 (UTC)

I remark that the use of the big O here is non-standard and is meaningless. The little o in the exponent takes care of everything: adding a big O on the outside has no effect. This seems to be a mistake in the Handbook of Applied Cryptography (HAC) which has not yet been reported to the authors, but anyone who looks through the actual published scientific papers that use the notation will see that none use big O. I have been discussing this with user Nageh on his talk page. See User_talk:Nageh#General_Number_Field_Sieve. Scott contini (talk) 12:46, 10 August 2010 (UTC)

Adding a big O on the outside has the effect of making it only an upper bound. For example, the function n^1/4 is in O(n^1/2+o(1)), whereas it is not in n^1/2+o(1). The latter only contains functions of the form n^f(n) where f(n) converges to 1/2 as n goes to infinity.—Emil J. 13:04, 10 August 2010 (UTC)

EmilJ, that's a valid point. But it is still not the standard definition. Handbook of Applied Cryptography should not be considered the primary source on this topic. The published number theory papers that use it are the primary source. What published number theory papers use thie big O? I'm pretty sure Pomerance, H. Lenstra, and A. Lenstra never have a big O in any of their papers that use it. —Preceding unsigned comment added by Scott contini (talk • contribs) 20:57, 10 August 2010 (UTC)

I'm reposting my conclusion here. The complexity of the GNFS and other similar sub-exponential algorithms refers to the expected running time and not to an upper bound, thus the Big O outside is inappropriate. I have not been able to find sources other than the HAC that use a Big O in their definition of L. What is needed now are suitable (original?) references for inclusion in the article, which define L without the Big O, both for the one and the two parameter version. Note that for the examples given on this article it does not matter whether they are given with or without the Big O (and in fact the GNFS would be more appropriately described without it). Nageh (talk) 07:55, 11 August 2010 (UTC)

Jafet's link to the Encyclopedia of Cryptography and Security entry on L-notation could indeed be a suitable link to be used here to rewrite the definition (the section is written Lenstra himself). Nageh (talk) 07:59, 11 August 2010 (UTC)

For the one parameter version, I would suggest using reference: Carl Pomerance, Analysis and comparison of some integer factoring algorithms, Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, 89-139. It can be downloaded from here: http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf . See Section 2. I don't know if Pomerance was the first to use it or not, but he definitely resolved the discrepancies among different analyses of factoring algorithms in the number theory literature in this paper. This is a classic paper. It has been cited 173 times according to Google scholar. I'm also pretty confident that the two parameter version came into being from the Number Field Sieve. Prior to that they were only using the one parameter version because the functions they were interested in always had $\alpha =1/2$. I've looked through the earliest two papers on the number field sieve ("The Factorization of the Ninth Fermat Number" and "The Number Field Sieve" by Lenstra Lenstra Manasse Pollard) and neither use the two parameter L-notation. I don't have my "The Development of the Number Field Sieve" book in front of me now, but I expect that it might have been first introduced there. Scott contini (talk) 23:41, 11 August 2010 (UTC)

Folks, I have the answer (thanks to Arjen Lenstra). The two parameter version was introduced by Arjen and Hendrik Lenstra in their "Algorithms in Number Theory" article. They introduced it to analyze a Coppersmith Discrete Log algorithm. See section 3.16 of https://openaccess.leidenuniv.nl/bitstream/1887/3825/1/346_085.pdf . So if nobody opposes, I would like to edit this article to cite this, and to remove the big O which only seems to be used by Handbook of Applied Cryptography (HAC) and sources that cite it. The standard definition does not involve any big O. BTW, I'm still chasing the history of the one parameter version, but Arjen told me the thinks Pomerance might have invented it in the Analysis and comparison of some integer factoring algorithms paper that I cited above. I hope to be to the bottom of this by tomorrow. Scott contini (talk) 07:17, 12 August 2010 (UTC)

Go ahead! Thanks for finding all this out! Nageh (talk) 07:30, 12 August 2010 (UTC)

Folks, I got to the bottom of the 1-parameter version and why the letter "L" was chosen. I emailed Carl Pomerance and he replied:

'Here's what I know, or seem to remember. I introduced the 1-parameter L notation in my paper "Analysis and comparison of some integer factoring algorithms" but not exactly in the way you write it. Instead of L_n[a], I wrote it as L^a, where the variable "n" was understood from context. I used the letter "L" only because there were various logs involved. I had been in the habit of labeling more complicated expressions with either an upper case or lower case "L" in earlier papers (for example see p.184 of my paper "On the distribution of amicable numbers, II", which is from 1981 and is #30 on my website)." '

We should add a history sub-section. Scott contini (talk) 21:46, 12 August 2010 (UTC)

Note that if you add a history section be careful that the information can be referenced. You may certainly tell that the one-parameter version was first found in a paper by C. Pomerance, and that it got subsequently adapted later by other authors, ultimately leading to the current two-parameter version. Anyway, a few words about historical introduction of the notation would certainly be interesting. We may also add a Properties section according to [2]. Nageh (talk) 10:02, 13 August 2010 (UTC)

Would this be accurate for the introduction?

Too confusing to me until I reached the, "When alpha is 0..." So here:

L-notation is used for growth between polynomial and exponential growth with respect to the length of $n$.

--72.226.86.106 (talk) 08:44, 6 April 2014 (UTC)

Clarification needed

I struggled understanding this until I realized that the o(1) added to c represents any function whose limit is 0 as n approaches infinity. This follows from the limit definition of small-o:

f is o(g) means that lim_{x-->inf} f(x)/g(x) = 0

When, as in the present case, g(x) = 1, f is o(g)=o(1) requires lim_{x-->inf} f(x) = 0.

A relevant example of what this means is what happens when multiplying by a constant factor d:

d * L(alpha, c) = d * exp( ( c + o(1) ) ln(n)^alpha ln(ln(n))^( 1-alpha ) )

= exp( ln(d) + ( c + o(1) ) ln(n)^alpha ln(ln(n))^( 1-alpha ) )

= exp( ( c + o(1) + ln(d)/( ln(n)^alpha ln(ln(n))^( 1-alpha ) ) ) ln(n)^alpha ln(ln(n))^( 1-alpha ) )

since ln(d)/( ln(n)^alpha ln(ln(n))^( 1-alpha ) ) approaches 0 as n approaches infinity, it can simply be absorbed by the o(1), so that d * L(alpha, c) = L(alpha, c)

Since L has to parameters, the article should discuss their respective impacts and in the same vein perhaps provide some rules of thumb on how minimization of each should be prioritized for the sake of science or of communication. (If that makes sense.)

L(1, c) = exp( ( c + o(1) ) ln(n) ) = n^( c + o(1) )

L(0, c) = exp( ( c + o(1) ) ln(ln(n)) ) = ln(n)^( c + o(1) )

L(alpha, c) interpolates between the two.

The following may be unfamiliar/nonobvious to some readers: ln(n) may represent the length of representation of a number n. When stating that "AKS is has polynomial complexity", it is implicitly understood to refer to a polynomial in ln(n), where n is the number to be tested. Otherwise, even naïve trial division by all integers smaller than n has "polynomial complexity" in n (i.e. at most O(n^3) or so, if division is O(n^2)).

Note that despite the two parameters, L notation is less general than big-O and little-o notation, although more "precise", since it bounds the function asymptotically from both sides. It simply does not cover functions that grow faster than polynomial with n. To cover exponential growth, I guess one could define something like:

L_e(alpha, beta, gamma, c) = exp( ( c + o(1) ) n^(alpha/(alpha+beta+gamma)) ln(n)^(beta/(alpha+beta+gamma)) ln(ln(n))^(gamma/(alpha+beta+gamma)) )

or, sacrificing the exp( ( c + o(1) ) ln(ln(n))^gamma ) part, just:

L_e(alpha, c) = exp( ( c + o(1) ) n^alpha ln(n)^( 1-alpha ) )

But this would still not cover fast-growing functions like n! and n^n.

Given the "notation abuse" issues with big-O (equality vs. set membership etc.), a clearer instruction on how to use L notation is warranted.

I am just scraping the surface of this topic, so I hope someone with the expertise will find my feedback useful for improving the article. Elias (talk) 10:03, 13 January 2023 (UTC)