Category: Number theory

Primon Gas

Today I’m going to be talking about an interesting little toy model in statistical mechanics – the Primon Gas.

Consider a physical system with a discrete energy spectrum

E = \{ \ln 2, \ln 3, \ln 5, ...\} = \{ \ln p : \text{p is prime} \}

Each energy in the spectrum corresponds to a particle with that energy. If we second quantize this system, we obtain a creation operator \alpha_{p} for each of these particles. Using these operators, we can act on a vacuum state (zero energy state), denoted | 1 \rangle, to obtain new states. We get the following ‘tower’ of states with corresponding energies:

\begin{array}{rcl}    \textbf{State} & \to & \textbf{Energy} \\    \alpha_2 | 1 \rangle & \to & \ln 2\\    \alpha_3 | 1 \rangle & \to & \ln 3 \\    \alpha_2 \alpha_2 | 1 \rangle & \to & \ln 4 \\    \alpha_5 | 1 \rangle & \to & \ln 5 \\    \vdots    \end{array}

Continue reading

Advertisements

Sum-Product Cycles of Positive Integers Pt. 3

To recap, we are attempting to find general solutions to the system of n coupled Diophantine equations with the form:

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1 .

We have already found that a solution is either compound (the concatenation of two shorter solutions), or it is simple (no consecutive subset is a solution to any shorter cycle). We have a canonical simple cycle, which for any pair (i, j) is the (i - 1)(j - 1)-cycle given by

[(i, j)]_{Can} = [(i, j), (1, i+j), (1, i+j+1), \ldots, (1, ij-1)]

As we shall see in this third (and final) post, the canonical cycle is very significant in the classification of simple solutions, and hence of all solutions.

Continue reading

Sum-Product Cycles of Positive Integers Pt. 2

Recall the sum-product n-cycle that we examined in this post. We seek simultaneous solutions to the coupled system of n Diophantine equations

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1.

We found some particular instances of complete descriptions of B_n, the set of equivalence classes of solutions (equivalence under commutation of the operations or of cyclic permutation of the indices i = 1, 2, \ldots, n). Now we seek a more powerful machinery with which to find and classify solutions.

Continue reading

Sum-Product Cycles of Positive Integers

Introduction

So in this post I’m going to talk a bit about a nice little number-theoretic problem that has been rattling around in my head a bit over the last few weeks. I’m essentially looking at the solutions (for each integer n) to a system of n coupled second-order Diophantine equations. The equations involved have a nice internal symmetry and I have a couple of theorems giving a complete classification of the solutions for each n – at least for positive integer solutions.

Let’s look at the prototypical equation we want to generalise:

a + b = ab \qquad a, b \in \mathbb{Z}^+.

Clearly the only viable solution to this is setting (a, b) = (2, 2) – it’s a very strong condition for two natural numbers to satisfy. However, it is a very aesthetically pleasing equation, so we would like to consider some extensions, and indeed a couple present themselves immediately.

One possible extension, which I am not going to consider here, is to find n-tuples of positive integers (x_1, x_2, \ldots, x_n) which satisfy

\sum_{i = 1}^n x_i = \prod_{i = 1}^n x_i.

((We observe immediately that the n-tuple (1, 1, \ldots, 1, 2, n) always works – but can you find how to generalise this to other n-tuples? What about those guaranteed to contain a certain subset of positive integers \{x_i, x_j, \ldots, x_k\}? What about finding the number of unique solutions for each n? You can read more about this in [1].))

The extension I will be looking at is the following: consider n many Diophantine equations of the form

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1.

Does such a system of equations always have a solution? How many solutions are there for a given n? What structure exists on the set of solutions? Clearly the solutions themselves are invariant under pair commutation ((x_i, y_i) \mapsto (y_i, x_i)) and under cyclic permutation of the indices (i \mapsto i + k (\mathrm{mod})_n). This kind of structure – where we have both an overall permutation of blocks and an underlying, independent permutation within each block – is realisable as the action of a wreath product on our space of objects. Let’s formalise this.

Definition 1

Let the n many coupled Diophantine equations of the above form be called the sum-product n-cycle, or just the n-cycle. Let A_n denote the set of n-tuples of pairs of positive integers which satisfy the n-cycle. That is,

A_n \subseteq ((\mathbb{Z}^+)^2)^n.

Let \Omega = S_2 \wr \mathbb{Z}_n denote the regular wreath product of S_n, the permutation group of two elements, and \mathbb{Z}_n, the group of integers modulo n. Furthermore let elements of \Omega act upon A_n with the primitive wreath action. We take the quotient space by this action,

B_n = A_n / \Omega,

to be our space of n-cycle solutions.

And let’s immediately disregard this formalism for the time being. We need to focus first on coming to grips with what an n-cycle is, and how it’s solved. Let’s look at some small-n solutions. Continue reading

Quantum Cryptography

[Accompanying notes for Physsoc (University of Canterbury) seminar on 2/8/2013]

Cryptography consists of making and breaking methods to communicate information without third parties which are able to intercept communications being able to gain knowledge of this information.

1. Cryptography before Quantum Mechanics

In the traditional example Alice and Bob wish to communicate privately despite Eve (who wishes to know what Alice and Bob are communicating) being able to intercept their communications. However in reality the situations in which cryptography has been used is for spies when letters are being intercepted, for the military — especially after the invention of radio, and today on the internet when we access online bank accounts and complete other online transactions.

In order to do this Alice and Bob could try to disguise their message (for example invisible ink or microdots), or they can employ a cipher scheme. The problem with a disguised message is that if a third party discovers the method of hiding the message they can immediately read all following messages. A cipher can be seen as an invertible function mapping the plain text to the enciphered text. The recipient can then apply the inverse function to discover this message. (Note: Strictly speaking f does not have to be a function, f^{-1} needs to be a function so it gives a unique message that was sent however the enciphering process can give multiple possible encrypted messages from which one can be randomly chosen.)

However this seems to have the same disadvantage — as soon as the inverse function is discovered messages can immediately be read, so in general we use a function of both the message and a key.  Thus even if the function in question is known, without the key which can be regularly changed it may still be possible to maintain security. However as the next example will show security of the key is not sufficient as this may be derivable from the message.

Example 1: Substitution Cipher

Alice and Bob map each letter of the alphabet to another letter. As there are 26! such bijective mappings this is too many for Eve to go through in any reasonable time. However in the English alphabet not all letters are used in equal frequencies in normal text. Hence if we look at the statistical distribution of the various letters in a large section of cipher text, we can identify this with the statistical distribution of letters in normal English, thus allowing us to find the key (the specific bijection used). Also the frequency of combinations of two or more letters in consecutive order can be used. The English language (or any other natural language) only uses a tiny proportion of all possible sequences of characters, the unique properties of the subspace of character sequences can be used in breaking several encryption schemes.

So we also need a function such that there is no such method to determine the key that is implementable in a the length of time we require the message to be secure for given the computing power at the disposal of Eve.

Example 2: One Time Pad

For simplicity we write the message as a string of zeros and ones. As a key we have a random string of zeros and ones of equal length which we only use for this message and never reuse. Then we apply the AND operation (addition modulo 2) to the nth digits of the key and the message to give the nth digit of the encrypted message. The reason this is unbreakable is that given an encrypted message there is a key such that any message of the correct length could be encrypted to give this message. As the key is random and never reused we can not use the keys that would correspond to given messages to determine which is the actual key used, and hence the actual message sent.

The problem is this requires Alice and Bob to have met before in secret and have exchanged an equal amount of data to that which they will in the future wish to communicate, not to mention the added complexity of generating random numbers — which by definition can not be done algorithmically — all random number generators on computers without specific hardware that uses electronic noise or other physical phenomena to generate random numbers, are only using some algorithm to generate pseudorandom numbers. For application such as internet banking this is clearly not highly feasible.

However in the last century there was a revolution in cryptography — public key cryptography. There are two approaches to this. In this Alice and Bob both create a secret number, transmit partial information about this and use this to create a key known to both parties which can’t be created from the partial information. Continue reading

The zero-free region of the Riemann zeta function

In the previous post about the zeta function the Vinogradov–Korobov zero-free region was stated, together with what it tells us about the error term involved in using {\text{Li}(x)} to approximate {\pi(x)}. In this post it is examined how this zero-free region, together with various other zero-free regions can be derived.

The Zero-Free Regions

In the last post it was stated that it was known that only the trivial zeros of the zeta function lie outside of the strip {0 < \Re(s) < 1}. Inside this strip lie an infinite number of zeros which we refer to as the non-trivial zeros. It has been possible to produce some further restrictions on the region in which we know the non-trivial zeros lie, these results are known as the zero-free regions.

The symmetry of the location of zeros in the critical strip around both the critical line and around the real axis make it sufficient to consider zeros in the region {0.5 \leq \beta \leq 1} and {t \geq 0}. The symmetries of the zero set can then be used to derive similar results in the other three segments that the critical strip is divided into by the lines {\Re(s)=\frac{1}{2}}, and {\Im(s)=0}. For sufficiently large t the following inequalities hold for some constant c (which will be different for the different inequalities below): Continue reading

The Riemann Zeta Function and the Prime Counting Function

This post is the first of a short miniseries looking at the distribution of prime numbers and the zeta function. The aim of this post is to motivate the link between the zeta function and the prime counting function \pi(x). It is currently planned for later posts to cover the zero-free regions and also look at generalisations of the Riemann zeta function such as Dirichlet L-functions.

The Zeta Function

For \Re(s) > 1 we define the zeta function by

{\zeta(s)=\sum_{n=1}^{\infty}n^{-s}.}

We note that by comparison with the p-series \sum_{n=1}^{\infty}n^{-p},\ p \in \mathbb{R} which is known to converge for p>1 (and diverge for 0 \leq p \leq 1), this sum converges for s in the given region.

For other values of s \neq 1 we extend the zeta function by analytic continuation. This results in a meromorphic function with a simple pole at s=1.

The Euler product formula and \pi(x)

We will now show that for \Re(s)>1 the following identity holds:

{\sum_{n=1}^{\infty}{n^{-s}}=\prod_{p}(1-p^{-s})^{-1}.}

We can start with an intuitive heuristic justification which will then be made rigorous. Continue reading