Scholz conjecture

conjecture

Uses your system voice; voice and rate in settings.

Q643614Snapshot

≈ 2 min read

Names in other languages

  • caConjectura de Scholz
  • FrançaisConjecture de Scholz
  • ItalianoCongettura di Scholz
  • EnglishScholz conjecture
  • NederlandsScholz conjecture

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, the Scholz conjecture is a conjecture on the length of certain addition chains. It is sometimes also called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture, after Arnold Scholz, who formulated it in 1937, and Alfred Brauer, who studied it soon afterward and proved a weaker bound. Neill Clift has announced an example showing that the bound of the conjecture is not always tight.

Statement

The conjecture states that , where is the length of the shortest addition chain producing n. Here, an addition chain is defined as a sequence of numbers, starting with 1, such that every number after the first can be expressed as a sum of two earlier numbers (which are allowed to both be equal). Its length is the number of sums needed to express all its numbers, which is one less than the length of the sequence of numbers (since there is no sum of previous numbers for the first number in the sequence, 1).

Computing the length of the shortest addition chain that contains a given number can be done by dynamic programming for small numbers, but it is not known whether it can be done in polynomial time measured as a function of the length of the binary representation of . Scholz's conjecture, if true, would provide short addition chains for numbers of a special form, the Mersenne numbers.

Example

As an example, : it has a shortest addition chain 1, 2, 4, 5 of length three, determined by the three sums 1 + 1 = 2, 2 + 2 = 4, 4 + 1 = 5. Also, : it has a shortest addition chain 1, 2, 3, 6, 12, 24, 30, 31 of length seven, determined by the seven sums 1 + 1 = 2, 2 + 1 = 3, 3 + 3 = 6, 6 + 6 = 12, 12 + 12 = 24, 24 + 6 = 30, 30 + 1 = 31. Both and equal 7.

Therefore, these values obey the inequality (which in this case is an equality) and the Scholz conjecture is true for the case .

Partial results

By using a combination of computer search techniques and mathematical characterizations of optimal addition chains, showed that the conjecture is true for all . Additionally, he verified that for all , the inequality of the conjecture is actually an equality. The bound of the conjecture is not always an exact equality. For instance, for n=9307543 , l(2^n-1)\le 9307570 , with l(n)=29 .

Shortest addition chains OEIS sequence A003313

Text derived from https://en.wikipedia.org/w/index.php?oldid=1286134739 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot scholz-conjecture-073906-21ddadefef5d276b · hash 21ddadefef5d276b4c9adefe06274025579172f279459333deb50286fe866900 · captured 2025-04-17 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Scholz conjecture”, snapshot scholz-conjecture-073906-21ddadefef5d276b. https://encyclopegia.org/a/scholz-conjecture

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.