Integer multiplication below n log n: the exponent κ

Analogy

Picture numbering the pages of a book by hand: the thicker the book, the more digits each page number has, but they grow very slowly, since the book has to get far thicker to gain a single digit. The total work is the number of pages times the length of a page number: that is the shape of an n log n cost, with the pages standing for the digits of the numbers being multiplied. Going below n log n means finding a method where the work per page still grows, but slightly more slowly than the length of the page numbers. κ measures that "slightly": at zero you are back to n log n; the larger κ is, the wider the saving grows as the book gets thicker.

Where the picture stops

Writing out every page number cannot be avoided, whereas for multiplication nobody has proved that such a rate is unavoidable; and the rate describes gigantic numbers, not how long a calculation takes.

In the glossary : n log n and κ