This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/NotationMatters

From OeisWiki

Jump to: navigation, search

Notation matters


Knuth's notation for relatively prime

On November 4, 2010, the phi-torial of n A001783 was selected as the "Sequence of the Day". A001783 states in the title:
"The phi-torial of n is the product k, 1 ≤ k ≤ n, k relatively prime to n."
This was translated to the formula

 \prod_{i = 1}^{n - 1} \delta_1^{\gcd(i, n)} i

With Knuth's notation this could also be written as

 \prod_{\stackrel{ 1 \le k \le n}{k \perp n}} k

For me the second formula is much easier to parse and to understand than the first formula (just compare the formulas to the definition in plain English). And it does not presuppose the knowledge of the Kronecker delta. Moreover, Knuth's notation is easy to generalize without additional clutter (for an example see here).

However, to say that the first formula is not optimal would be an euphemism. To see this consider the strange name 'phi-torial'. Clearly this name relates to the factorial numbers.

 \prod_{1 \le k \le n } k

So we just have to add three symbols to this formula to go from the factorial to the phitorial. This is simple and intuitive; compared to that the first formula can be understood best as an elaborated way to conceal the intended meaning.

In 1989 Knuth, Graham and Patashnik wrote in a book which now is a standard reference (Concrete Mathematics):

Hear us, O mathematicians of the world! Let us not wait any longer! We can make many formulas clearer by defining a new notation now! Let us agree to write m ⊥ n, and to say "m is prime to n", if m and n are relatively prime.

To say 'a is prime to b' is for me a good arithmetical overload of the geometrical 'a is orthogonal to b' and agrees well with my intuition.

I do not understand why 21 years later some people still stick to cumbersome 19th century notation as some simple "changes would improve the current situation and make it easier on all future mathematicians".

The perils of bad notation

In the meantime Alonso del Arte draw my attention to the fact that the Kronecker-delta-based formula as displayed above is plain wrong. Indeed it computes the phitorial for n ≥ 1 as 1, 1, 2, 0, 24, 0, 720, 0, 0, 0, ...

Now this is an important observation as it shows that the use of the Kronecker-delta-based formula requires some kind of additional thought; this is in contrast to the use of `knยด which is just attached to the summation symbol without any further consideration or changes to the main formula. The benefit clearly is: the danger to produce errors is thereby almost eliminated. Likewise the chance that a manifest error is overlooked because hidden in some complex notation is reduced.

Thus Alonso del Arte's observation highlights what constitutes a good notation.

A second example

\Omega(n) = \delta_{1}^{\{\pi(n) - \pi(n-1)\}} + 
\delta_{0}^{\{\pi(n) - \pi(n-1)\}} \sum_{i = 1}^{\pi(\lfloor\sqrt{n}\rfloor)} 
\sum_{j = 1}^{\lfloor \log_{p_i} n \rfloor} \delta_{\big\lfloor 
\frac{n}{{p_i}^j} \big\rfloor}^{\big\lceil \frac{n}{{p_i}^j} 

Whoever wants to see such a monster? What does it say? What insight does this formula give? Who needs this? In my eyes it is just thieving the time of the reader who tries to parse it. Such a formula is notational humbug. [Humbug = creating public sensations and fascination with a circus of bad notation.] Such formulas should in my opinion be exhibited in television shows like 'Pimp-My-Formula' but not on the OeisWiki. Moreover, this formula does not employ the notion and notation of p-adic order, which is fundamental here. The following two sentences (adapted from Wikipedia) could replace most of the introduction of the article about Omega .

In number theory, for a given prime number p, the p-adic order of a number n is the highest exponent ν such that pν divides n; it is commonly abbreviated νp(n). Ω(n) is the total number of prime factors of n; thus

 \Omega(n) = \sum_{{p \mid n} \atop {p ~ {\rm prime}}} {\nu_{p}(n) }.

See also

Personal tools