Skip to main content

Featured Post

Ed Scheidts Mayan Symbols - Can we solve the puzzle?

In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...

Infinite Regular Primes Conjecture

Another unproven conjecture in number theory is the Infinite Regular Primes Conjecture (IRPC). It addresses a special properties of primes. A prime can be regular or a prime can be irregular. For the later we know a proof [given below] since many years. For regular primes it is still unknown if they are infinite despite the fact that we can give good arguments that around $$60.653\%$$ of all primes should be regular. So we know that major part of all primes should be regular, but we cant prove it.
A regular prime can be characterised in more than one way.

Definition [Regular Prime]
A prime \(p > 2\) is called regular if it does not divide the class number of the \(p\)-th cyclotomic field $\blacktriangleleft$.

An alternative characterisation is the following.

Definition [Regular Prime]
A prime \(p > 2\) is called regular if it does not divide the numerator of any Bernoulli number \(B_n\) for \(n = 2,4,6,...,p-3\) $\blacktriangleleft$.

Then the IRPC conjecture simply this:

Infinite Regular Primes Conjecture
There are infinite many regular primes.

Kummer proved in 1850 that Fermat's Last Theorem is true if the involved exponent $p$ is regular. The infiniteness of irregular primes has already been proved several decades ago (1954) by Carlitz [1]. His proof is based on the second characterisation from above. It is a proof by contradiction. He assumes that there are only finite many irregular primes, which leads him to a contradiction to some proven result about Bernoulli numbers.

Proof (Infinite Irregular Primes). [Following Carlitz [1]]. For the proof Carlitz uses several properties of the Bernoulli numbers:

  1. \(B_m \equiv 0\pmod{p^r}\) if \(p^r | m\) and \((p-1) \nmid m\)
  2. \(pB_m \equiv -1\pmod{p}\) if \((p-1)|m\)   (Staudt-Clausen Theorem)
  3. \(\frac{B_{m+r(p-1)}}{m+r(p-1)} \equiv \frac{B_m}{m}\pmod{p}\)   (Kummer's Congruence)

Contradiction assumption: The number of irregular primes is finite, say \(p_1,p_2,...,p_k\).

We build the integer \(M = 2^t\prod^k_{i=1}(p_i-1)\), for an arbitrary integer \(t\) that we need later. The denominator of the \(m\)-th Bernoulli number is defined as \(\prod_{(p-1)|m}p\). We build the quotient $$ \frac{B_M}{M} = \frac{N_M}{M\cdot D_M} $$ whereof \(N_M\) is the numerator of the \(M\)-th Bernoulli number and \(D_M\) its denominator. If we plug in in the values for \(M\) and \(D_M\) we get $$ \frac{B_M}{M} = \frac{N_M}{2^t\prod^k_{i=1}(p_i-1)\cdot \prod_{(p-1)|M}p}$$ Note that in the denominator \(D_M = \prod_{(p-1)|M}p\) all irregular primes are contained. Now take item 2 from above, i.e., $$p_iB_M = \frac{N_M}{\prod_{(p-1)|M}p} \equiv -1\pmod{p_i}$$ which holds for every irregular prime \(p_i\). It follows, since non of them yields zero, that \(N_M\) does not contain any of the primes \(p_i\). Thus the only primes that can be contained in \(N_M\) are, according to item 1., factors of \(M\). So the new numerator \(N'_M\), after cancellation with \(M\) is

$$ \frac{B_M}{M} = \frac{N_M}{M\cdot D_M} = \frac{N'_M}{D'_M}$$

and $N'_M$ must be equal to $\pm 1$, since no irregular prime is contained and all other possible factors have been cancelled out by division with \(M\) $$ \frac{B_M}{M} = \pm \frac{1}{D'_M}$$ The contradiction now occurs, because it is well known that

$$ \lim_{m \rightarrow \infty}{\frac{B_m}{m}} = \infty$$

However, the \(t\) in the definition of \(M\) could be arbitrary large. So one could use this freedom to establish.

$$ \lim_{M \rightarrow \infty}{\frac{B_M}{M}} = \lim_{M \rightarrow \infty}{\frac{1}{D'_M}} = 0$$

, so the assumption that there are only finite irregular primes is wrong.

Q.e.d.

If one wants to use a similar approach to prove that there are infinite regular primes, he will probably fail, since he could not construct an object (like the \(M\)-th Bernoulli number) that contains all finite regular primes in a similar easy way.

Heuristics arguments also suggest that the fraction of regular prime is even larger. It is estimated that around \(60.64\%\) are regular.

Based on calculation from the blog post The Agoh-Guiga Conjecture, one could give another characterisation of a regular prime

Definition [Regular Prime, Reformulation]
An odd prime \(p\) is regular if there is no even number \(1 \leq n \leq p-3\) such that $$\sum^{(p-1)/2}_{k=1}k^{n-1} \equiv 0\pmod{p}\;\text{and}\; p\nmid (2^n-1)$$

Proof. Since it holds that (see The Agoh-Guiga Conjecture) $$\sum^{(p-1)/2}_{k=1}k^{n-1} \equiv n^{-1}2^{-n}2(1-2^n)B_n \pmod{p}$$ the term can only be zero if either $(1-2^n)$ is divisible by $p$ or $B_n$. Since we excluded the former per definition the claim follows.
Q.e.d.

Note that a regular prime number $p$ with $p | (1-2^n)$ (as well as $B_n$) is not covered by the reformulation.
If we neglect the requirement that $p\nmid (2^n-1)$ for the moment. Is it easier to prove that there exists infinite many primes with the property that $$\sum^{(p-1)/2}_{k=1}k^{n-1} \not\equiv 0\pmod{p}$$ for all even $n \leq p-3$?
That means, one could perhaps show that for infinitely many primes
$$ \prod^{(p-3)/2}_{j=1}\sum^{(p-1)/2}_{k=1}k^{2j+1} \not\equiv 0\pmod{p}$$ hold.

Also the density heuristic can be easily derived from the reformulation. The sum $\sum^{(p-1)/2}_{k=1}k^{n-1}$ should be not equal to zero, for all even $n$ less than $(p-3)/2$. Hence $(p-1)/p$ values are valid sum results. If we consider this for all $(p-3)/2$ even integer less than $p-3$ , we have
$$ \lim_{p \rightarrow \infty}{\prod^{(p-1)/3}_{j=1}\frac{p-1}{p}} = \left(1 - \frac{1}{p}\right)^{(p-3)/2} \approx \frac{1}{\sqrt{e}} \approx 0.60653$$
which yields also around $60.65\%$.

[1] Carlitz, L. (1954). "Note on irregular primes". Proceedings of the American Mathematical Society (AMS) 5: 329–331

Comments

Popular posts from this blog

Kryptos - The Cipher (Part 4) - Correctly positioned decryption of the word BERLIN

EASTNORTHEAST - This is not exactly the hint Jim Sanborn (JS) gave for K4 on the 29th of January this year. He only gave NORTHEAST - which refers to the positions 26-34 of K4's plaintext.  Beside BERLIN and CLOCK it is the third revealed plaintext word of K4. However, also this hint does not seem to help much.  However, it just so happened, that a member in the yahoo kryptos group had a conversation with Jim Sanborn due to a submitted solution. Sandborn's answer to the question contained again the last clue which surprisingly was EASTNORTHEAST at position 22-34. Jim Sanborns compass rose at CIA There is disagreement if Jim revealed this on purpose or he did it accidentially, but the new extended clue seem to be serious and valid.Interestingly, EASTNORTHEAST is exactly the direction which is illustrated on the compass rose on one of the stones around kryptos, also created by Jim Sanborn. Actually, i dont really kn...

Kryptos - The Cipher (Part 1) - Introduction

Introduction. Since I think that KRYPTOS does not need any introduction, I will only give you a brief description of one of the most famous and only partially solved ciphers known today: KRYPTOS - Von Jim Sanborn - Jim Sanborn, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=8253447 KRYPTOS was constructed in Nov. 1990 on the ground of the CIA Headquarter in Langley, Virginia by Jim Sanborn It contains 4 ciphers (K1,K2,K3,K4) on its left side and some kind of Vigenère-Table on its right side K1, K2 and K3 were solved by James Gillogly in 1999. Afterwards, the CIA and later the NSA claimed that they had a solution to the first three ciphers at an earlier point in time Ed Scheidt, a cryptoanalyst and former director of the CIA, gave Sanborn the input of possible cryptographic techniques to use K1 is a variant of the Vigenère-Cipher (Quagmire 3) with the codewords KRYPTOS and PALIMPSES...

Kryptos - The Cipher (Part 3)

This post is about is more or less a collection of several approaches and facts that has been said as well as some speculations. B-ary integer representation According to [1] during a Question and Answer round, Jim Sanborn was asked again about the hint BERLIN. The question was if N decodes to B, Y decodes to E, etc, etc. and Jim confirmed it does. Emphatically . It is written, that Jim Sanborn rattled through the entire crib: \begin{align}   \texttt{N} &\stackrel{\text{decode}}{\rightarrow} \texttt{B} \\   \texttt{Y} &\stackrel{\text{decode}}{\rightarrow}  \texttt{E} \\   \texttt{P} &\stackrel{\text{decode}}{\rightarrow}  \texttt{R} \\   \texttt{V} &\stackrel{\text{decode}}{\rightarrow}  \texttt{L} \\   \texttt{T} &\stackrel{\text{decode}}{\rightarrow}  \texttt{I} \\   \texttt{T} &\stackrel{\text{decode}}{\rightarrow}  \texttt{N} \end{align} When the same q...