Project 2: Cyclic Difference Sets

Introduction

The goal of this project is to explore cyclic difference sets using modular arithmetic. For an integer $m$, a cyclic difference set modulo $m$ is a subset of the set of integers modulo $m$ such that the differences between every element of the cyclic difference set generates every element of the integers modulo $m$ the same number of times. Specifically, this project explores numerically a method of generating cyclic difference sets by using the squares of integer sets. Various conjectures are made and proven with respect to this method.

Theory

Modulo

We define two numbers $a$ and $b$ to be congruent modulo $m$ as $a \equiv b$ (mod $m$). Consequentially, $a - b$ is divisible by $m$. For a positive integer $m$, we define $\mathbb{Z}/m\mathbb{Z}$ as the set of integers modulo $m$. $\mathbb{Z}/m\mathbb{Z}$ contains all nonnegative proper remainders upon division by $m$. In other words, $\mathbb{Z}/m\mathbb{Z} = \{0, 1, 2, \dots, m-1\}$. It is important to note that $\mathbb{Z}/m\mathbb{Z}$ is closed under addition and multiplication, meaning that any arithmetic operations on the elements of $\mathbb{Z}/m\mathbb{Z}$ result in an integer in the set $Z/mZ$.

Example: $m$ = 7

We demonstrate some calculations modulo $7$ here in order to set the stage for more complicated calculations in later sections.

For $m=7$, $Z/7Z = \{0, 1, 2, 3, 4, 5, 6\}$. Since $8 / 7 = 1$ remainder $1$, $8 \equiv 1$ (mod $7$). $6 + 6 = 12 \equiv 5$ (mod $7$).

Inverses

Although we state that $\mathbb{Z}/m\mathbb{Z}$ is closed under addition and multiplication, we have not shown until this section specifically how $\mathbb{Z}/m\mathbb{Z}$ is closed under subtraction. The additive inverse of an integer $x$ in $\mathbb{Z}/m\mathbb{Z}$, denoted by $-x$, is the integer such that $x - x = 0$. For example, for $m = 7$, the additive inverse of $3$ is $4$ since $3 + 4 = 7 \equiv 0$ (mod $7$). Below we will raise some conjectures and provide reasoning for their proofs.

Conjecture 1: If $x$ is in $\mathbb{Z}/m\mathbb{Z}$ and $y = -x$, then $x^2 \equiv y^2$ (mod) $m$.

Since $y = -x$, $y^2 = (-x)^2 = x^2$. Thus, it is true that $y^2 \equiv x^2$ (mod) $m$.

Conjecture 2: If $m$ is even and $x \not = \frac{m}{2}$, then $x$ is its additive inverse modulo $m$.

When $m$ is even, the number of elements in $\mathbb{Z}/m\mathbb{Z}$ is odd, so when $x = \frac{m}{2}$, x is its additive inverse modulo $m$.

Conjecture 3: The maximum number of distinct nonzero squares modulo $m$ when $m$ is odd is $\frac{m-1}{2}$. The maximum number of distinct nonzero squares modulo $m$ when $m$ is even is $\frac{m}{2}$.

Conjecture 3 follows from Conjectures 1 and 2. There are $m-1$ distinct nonzero elements in $\mathbb{Z}/m\mathbb{Z}$. When the elements of $\mathbb{Z}/m\mathbb{Z}$ are squared, it is true from Conjecture 1 that the squares of integers in $\mathbb{Z}/m\mathbb{Z}$ and their additive inverses are equal. This repitition of squares results in $\frac{m-1}{2}$ distinct squares.

Squares¶

To create our cyclic set, we need to approach this in steps. Our first step is to create, as this section implies, a set of squares. Given a modulus $m$, our set will consist the square of every element modulo $m$ between 1 and $m - 1$. We can calculate this by hand rather quickly when dealing with a small modulus like $m = 7$, but when dealing with numbers like $m = 101$, we need a program. We will show $m = 7$ as an example in our program.

This program creates an array and stores the square of each natural number as an element, labeled with that natural number's index.

Let's look at this set of squares. $1^2 \equiv 1(\bmod 7)$, $2^2 \equiv 4 (\bmod 7)$, $3^2 \equiv 2(\bmod 7)$, $4^2 \equiv 2(\bmod 7)$, $5^2 \equiv 4(\bmod 7)$, and $6^2 \equiv 1(\bmod 7)$. We have 3 distinct answers: 1, 2, and 4. Similarly, if we run this program with these select modulo, we get the following results:

From here, we start to note a definite pattern summed up in this formula: For our distinct number of elements k in our cyclic set D, $k = \frac{m - 1}{2}$. However, just like m, k must also be a natural number, as we cannot have a decimal answer for an exact number of elements. Let's factor the formula.

$k = \frac{m - 1}{2}$

$2k = m - 1$

$m = 2k + 1$

By definition of odd terms, m is an odd number. Therefore, m must be odd in context of this problem.

Now we'll prove something interesting. Let's assume, for some integer $a \in \mathbb{Z}$, that our modular $m = a^2$. If we know that m is odd, then therefore a must also be odd. But we also know that for this case, $k < \frac{m - 1}{2}$. This is distinctly different that what we stated just above. We will explore this further in our proof section.

Differences

Now let us get into the meat of a cyclic difference set: the differences. From here, let us clarify the conditions that makes our differences cyclic. Firstly, if we have a set of modulo m, then the differences of the distinct nonzero squares must include every natural number from 1 to m - 1. Otherwise, our set is not cyclic. Secondly, these differences must appear the exact same number of times. We will call this number of occurences lamda. Similarly to differences, calculating this by hand is not difficult, but simply tedious. We will instead look at code highlighting this. We will once again use m = 7.

Recall from Squares that we have 3 distinct squares: 1, 2, and 4. In modulo 7, they form every difference between 1 and (7 - 1). But also, for our lambda ($\lambda$), we have a value of 1 for every distinct difference. We have the same value of $\lambda$ for every equation. Thus, when m = 7, we have a cyclic differences set. Let's look at a table of more modulos that work.

From here, we start to notice a distinct pattern. $\lambda = \frac{m - 3}{4}$. This formula works for all legitimate value of m. We will prove this formula in a later section, as well as what defines a legitimate value of m. Before that, let's factor $m = 2k + 1$ into the equation.

$\lambda = \frac{2k + 1 - 3}{4}$

$\lambda = \frac{2k - 2}{4}$

$\lambda = \frac{k - 1}{2}$.

As we can see her, our formula for $\lambda$ in terms of k matches our formula for k in terms of m. This entails that we can rewrite our equation as such:

$k = 2 \lambda + 1$.

Our number of distinct squares k is therefore also absolutely an odd number when our modular m is an odd number.

Proof

Formula for $k$

To find a formula for $k$ in terms of $m$, we first found different $m$ values that produce cyclic difference sets and checked what the $k$ value for each one was. Through this method, we conjure that $k = \dfrac{m-1}{2}$ for all $m$ that produce a cyclic difference set. In order to prove our conjecture, we have to logically explain it. $k$ is defined as the number of elements in $D$. Since $D$ only contains nonzero elements, the total possible elements in $D$ is $m-1$. However, the squares of additive inverses are congruent modulo $m$ and $D$ does not contain any repeats of its elements. So, by Conjecture 3 in Inverses, the number of elements in $D$ when $D$ is a cyclic difference set is $\dfrac{m-1}{2}$. Thus, $k = \dfrac{m-1}{2}$.

Formula for $\lambda$

To find a formula for $\lambda$ in terms of $m$, we used the same method we did for $k$. Through this method, we conjecture that $\lambda = \dfrac{m-3}{4}$ for all $m$ that produce a cyclic difference set. We will prove this conjecture by logically explaining it. $\lambda$ is defined as the number of pairs of elements of $D$ giving each nonzero difference modulo $m$. We know that there are $k$ elements in $D$ by the definition of $k$, we use these elements to set up a chart. The top and leftmost lines are the elements of $D$ in the same order. The rest of the chart is the differences of every element of $D$ found by taking the top number and subtracting the leftmost number, modulo $m$. If the difference is a negative number, then it is replaced with its additive inverse modulo $m$. These differences should represent all of the nonzero elements of $\mathbb{Z} / m\mathbb{Z}$ an equal number of times. For example, we will do the chart for $m=7$.

We will use the chart to prove our conjecture that $\lambda = \dfrac{m-3}{4}$. There are $k^2$ differences in the chart, but we only want the nonzero elements. The zeros will only appear on the diagonal from top-left to bottom-right, which includes $k$ zeros, so we're only looking at $k^2 - k$ differences. This gives us the amount of nonzero differences in the chart, but we want the number of times each one shows up. Since there are $m-1$ nonzero elements of $\mathbb{Z} / m\mathbb{Z}$, we now have $\lambda = \dfrac{k^2 - k}{m-1}$. Since we want $\lambda$ in terms of $m$, we will substitute $k = \dfrac{m-1}{2}$. The new equation is $\lambda = \dfrac{\dfrac{(m-1)^2}{2^2} - \dfrac{m-1}{2}}{m-1} = \dfrac{m-1}{4} - \dfrac{1}{2} = \dfrac{m-3}{4}$. Thus, $\lambda = \dfrac{m-3}{4}$.

Conclusion

Finding a General Form for $m$

We're trying to prove the claim that if $D$ is a cyclic difference set, then $m$ has a particular form. We will start by letting $D$ be a cyclic difference set. Since $D$ is a cyclic difference set, we know $k = \dfrac{m-1}{2}$ and $\lambda = \dfrac{m-3}{4}$. If we solve both of these equations for $m$, we have $m = 2k + 1$ and $m = 4\lambda + 3$. To find just one equation for $m$, we will sum both equations. This leads us to $2m = 2k + 4\lambda + 4$, which can be simplified to $m = k + 2(\lambda + 1)$. Therefore, if $D$ is a cyclic difference set, then $m = k + 2(\lambda + 1)$.