Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

Integral triangles



with integral medians
Jonathan Ringstad
An integral triangle is a triangle in euclidean space where all side-lengths $a$, $b$ and $c$ are natural numbers, as well as the area.
The triangles under consideration do not only have to be integral triangles, but are also required to have medians $m_a$, $m_b$ and $m_c$ with integral length.

Area


By Heron's formula, the area of a triangle is given as \[ A = \frac{1}{4}\sqrt{(a^2 + b^2 + c^2)^2 - 2(a^4 + b^4 + c^4)}. \] Shuffling around a few symbols, we get that given $a, b, c, A \in \mathbb{N}$, the equation \[ 2a^2b^2 + 2a^2c^2 + 2b^2c^2 - a^4 - b^4 - c^4 - 16A^2 = 0 \] must be true so that we can call our triangle integral.

Medians


Looking at the medians next, we know that the median $m_a$ cutting the side-length $a$ of the triangle in half, can be computed from the side-lengths by \[ m_a = \sqrt{\frac{2b^2 + 2c^2 - a^2}{4}}. \] This gives us the equation \[ 2b^2 + 2c^2 - a^2 - 4m_a^2 = 0. \]
The other medians are computed as \[ m_b = \sqrt{\frac{2a^2 + 2c^2 - b^2}{4}} \] and \[ m_c = \sqrt{\frac{2a^2 + 2b^2 - c^2}{4}}. \] As we can see, they are simply permutations of variables on the same formula.

The problem

We are now ready to state the complete problem.

Find all natural numbers $0 \le a, b, c, m_a, m_b, m_c, A \le 1000$ that form a valid triangle, and satisfy the following system of diophantine equations:
\[ 2a^2b^2 + 2a^2c^2 + 2b^2c^2 - a^4 - b^4 - c^4 - 16A^2 = 0, \] \[ 2b^2 + 2c^2 - a^2 - 4m_a^2 = 0, \] \[ 2a^2 + 2c^2 - b^2 - 4m_b^2 = 0, \] \[ 2a^2 + 2b^2 - c^2 - 4m_c^2 = 0. \]
Putting the question into different terms, are there small integral triangles with integral medians? If so, what are they? If not, why not? And can we prove it?
A natural generalization of the question (which, as of today, remains an open problem) is do any integral triangles with integral medians exist at all? If yes, can we devise a good algorithm to find them? If no, why, and can we prove it?

Diophantine equations?

A diophantine equation is a polynomial equation in $\mathbb{Z}[a_1, a_2, \dots, a_n]$, that is, a polynomial equation with integer coefficients, describing an algebraic curve, surface or hypersurface. The only admissible values for the indetermines are integer values.
Typical questions surrounding Diophantine equations are such as
  • Are there any solutions?
  • Are there finitely or infinitely many solutions?
  • Can we find all solutions or somehow describe them?
  • In our case, we are considering a system of diophantine equations, so we are looking for solutions that satisfy all of our diophantine equations simultaneously.

    Miscellania

    Before we dive right into the matter, lets get some lemmas, notation and other administrivia out of the way.

    Notation

    We will let $D_A[\cdots]$ denote the diophantine expression describing the constraints on the triangles area, that is, $D_A[a, b, c, A] = 0$ is the full equation. Likewise, $D_{m_a}[\cdots]$, $D_{m_b}[\cdots]$ and $D_{m_c}[\cdots]$ describe the constraints on the medians.
    We will denote a solution $\mathbf{x} = (a, b, c, m_a, m_b, m_c, A)$, and call the set of all solutions $\mathbf{x}$ solving our system of equations $\mathbb{D}$. At times we will do calculations in finite rings/fields $\mathbb{Z}_n$, in which case we will denote all solutions in $\mathbb{Z}_n$ as $\mathbb{D}_n$.

    Lemmas

    The following lemmas will greatly simplify some of our descriptions; proofs are omitted in this presentation, but can be found in the actual paper.
    Lemma 1. Scaling the sides $a, b, c$ of a triangle by some factor $k$, will scale the medians $m_a, m_b$ and $m_c$ by a factor $k$.

    Lemma 2. Scaling the sides $a, b, c$ of a triangle by some factor $k$, will scale the area $A$ by a factor $k^2$.

    Definitions

    By lemma 1 & lemma 2 we immediately obtain an infinite number of solutions given a single solution, by simply scaling up $a, b$ and $c$. Most of these solutions will not give us any new information, so we define the notion of a primitive solution:
    Definition 1. Primitive solutions Given a solution $\mathbf x = (a, b, c, m_a, m_b, m_c, A)$ it is considered primitive if there is no natural number $k$ such that $k$ divides $a, b, c, m_a, m_b, m_c$ and $k^2$ divides $A$.

    Given a solution $\mathbf x = (a, b, c, m_a, m_b, m_c, A)$, by permuting around the sides $a, b, c$ of the triangle, we can produce a new solution, which will simply represent a rotated or reflected triangle. We will thus generally only consider solutions unique under such permutations.

    A first attempt

    The diophantine equation $D_A[a, b, c, A] = 0$ is the most complicated, so a simpler problem to attack is the system of 4 diophantine equations, ignoring the constraints for the area. For this system a particular solution is known, $\mathbf x = (68, 85, 87)$ giving rise to the rational medians $(79, 131/2, 127/2)$. Scaling this solution upwards by some $k$ will give us integral medians, however...
    Area$(k\cdot68, k\cdot85, k\cdot87) = 240k^2\sqrt{2002}$
    so we cannot obtain an integral area from this tuple.
    A solver was written to find more solutions to this reduced system, and in the range $0 \le a, b, c, m_a, m_b, m_c, A \le 1000$ it found 8 primitive, unique solutions;
    However...

    All of these solutions had again an irredeemably irrational area.

    A brute-force solution

    The next attempt was to brute-force the entire solution space.
    ▶ 7 variables
    ▶ Range: $0 \le x \le 1000$
    ▶ $10^{21}$ possible solutions

    ▶ Assuming a hypothetical computer that can take a candidate $\mathbf x$ and check whether it solves the system of equations in one cycle
    ▶ Runs at a leisurely 1GHz
    ▶ Approx. 31688 years of computations!
    Unfortunately no such computer actually exists, so by a very optimistic estimate, verifying a solution will actually take us at least a few hundred cycles. This would increase the order of magnitude of time we needby two or so, and even though we can shave off maybe two or three orders of magnitude by parallelizing the problem and running it on high-end machines, the amount of time required seems impossible... So lets take a break and talk about something different.

    Modular arithmetic

    Calculating solutions in a finite ring/field $\mathbb{Z}_n$.
    ▶ Easy to do for small $n$
    ▶ As $n$ becomes larger the difficulty approaches the brute-force solution
    ▶ We can throw back non-solutions from $\mathbb{D}_n$ to $\mathbb D$.
    If $\mathbf x \in \mathbb D$, then $\mathbf x \in \mathbb{D}_n$. Taking the contra- positive, we obtain \[ \mathbf x \not\in \mathbb{D}_n \Rightarrow \mathbf x \not\in \mathbb{D}. \]
    Examples:

    $\mathbb{Z}_2$:

          (0, 0, 0, 0, 0, 0, 0)
          (0, 0, 0, 1, 1, 1, 1)

    $\mathbb{Z}_3$:

          (0, 0, 0, 0, 0, 0, 0)
          (1, 1, 1, 0, 0, 0, 0)
          (2, 1, 1, 0, 0, 0, 0)
          (2, 2, 1, 0, 0, 0, 0)
          (2, 2, 2, 0, 0, 0, 0)
    Since the only solutions in $\mathbb{Z}_2$ are $a = b = c = 0$, we can deduce that there cannot exist any solutions where $a, b$ or $c$ are odd.
    Since the only solutions in $\mathbb{Z}_3$ are when $m_a, m_b, m_c, A$ are divisible by three, we can deduce that there are no solutions where $m_a, m_b, m_c$ or $A$ are not divisible by 3.
    Similar deductions can be made from larger rings, but these are the most useful. A program computing solutions in finite rings/fields can be found in the paper.

    Optimizations: The return of the bruteforce

    Now that we have developed a few more tools, we are able to apply some optimizations to the brute-force solution.
    ▶ Skip any $a, b, c$ that don't connect to a valid triangle
    ▶ Skip any $a, b, c$ that form a degenerate triangle ($A=0$)
    ▶ Skip any $a, b, c$ that are odd
    ▶ Skip any $m_a, m_b, m_c, A$ that are not divisible by three
    Additionally, given some $a, b, c$, and we notice that Area$(a, b, c)$ is not a natural number (in our range), we can skip all further tuples that involve said $a, b, c$ and any combination and multiples thereof.
    Although calculating how much this actually saves us in computing time might be equivalent to actually solving the problem in its general form, the advantage proved to be massive:
    384 Sandy-bridge Intel Xeon cores
    768 GiB of memory
    ▶ Written in C99; Conservative compiler flags with regard to numerical and algorithmic optimizations
    ▶ Roughly 1.4 hours until the entire parameter space was exhausted.
    No solutions found!
    This answers the first part of our research endeavour in the negative:

    There are no solution to our system of diophantine equations in the range $0 \le a, b, c, m_a, m_b, m_c, A \le 1000$.

    The remainder of the paper focuses on elaborating on the why, verifying the results we have obtained through alternative methods, and proposing ways to solve the general problem.

    More modular arithmetic

    Returning to our modular computation, lets compute some larger rings and observe how many solutions we get for each.

    Observations:


    ▶ Some rings $\mathbb{Z}_n$ only have one solution: The trivial one
    ▶ Most of them (but not all) seem to be prime
    ▶ $\mathbb{D}_n = \{\mathbf 0\}$ means any solution $\mathbf x$ has to be divisible by $n$

    Corollary:


    ▶ If we can prove there is an infinite sequence of numbers $x_n$ such that $\mathbb{D}_{x_n} = \{\mathbf 0\}$, no solutions can exist.
    ▶ If we can compute solutions for a large number of $n$, we can establish a lower bound that all solutions have to exceed.
    ▶ In fact; from the table above, we can deduce a lower bound lcm(5, 7, 17, 19, 29, 31, 35, 41, 43) = 17917712785.
    Computing solutions in $\mathbb{Z}_n$ still takes a bit of time. Calculating solutions only for fields $\mathbb{Z}_p$ where $p$ is prime, seems to be the most effective; if $n = a\cdot b$, it seems that there is a relation \[ |\mathbb{D}_n| \ge |\mathbb{D}_a|\cdot|\mathbb{D}_b|. \] This yields a very effective algorithm to push the lower bound very high.
    It seems that for most prime numbers, $\mathbb{D}_p = \{\mathbf 0\}$, which leads us to the following conjecture:

    Conjecture


    There exist no integral triangles with integral medians.

    Summary


    ▶ There are no solutions $0 \le a, b, c, m_a, m_b, m_c, A \le 1000$
    ▶ In fact, there are no solutions up to 17917712785, and an efficient algorithm has been presented that, assuming the conjecture is true, can be used to push the lower bound to arbitrarily large values.
    ▶ For a general proof, proving a sequence $x_n$ exists such that $\mathbb{D}_{x_n} = \{\mathbf 0\}$ seems to be the way to go.

    Thank you for your attendance.