A construction on an infinite 2d grid, part 1

Question

Recall the classic old problem where we're asked whether a line segment of specific length can be constructed with compass and straightedge, given an initial line segment of length 1? We're going to do something similar here.

---

Imagine there is a 2-dimensional space that is infinite, with all integer coordinates (e.g (5,3) is an integer coordinate, (7,-1.5) is not) dotted. You are going to do the following construction to get a specific number:

• draw 4 line segments that start and end on a dot
• these 4 lines should enclose a quadrilateral, triangles are not counted. (You can't enclose more than one quadrilaterals anyway.)
• the quadrilateral enclosed should be of a specific type

And the area of the quadrilateral is the number you have constructed.

The question being asked is, given a specific type of quadrilateral being restricted, what are the full set of numbers that we can construct this way?

In part 1, we're concerned with squares.

Note that obviously, the vertices of the quadrilateral can be at non-integer coordinates. They are only required to be the intersection of two line segments.

---

Obvious, all square numbers are trivial to construct:

Non square numbers, like 5 or 0.5, requires a bit more effort:

Some numbers can be very hard to be constructed: e.g 0.8(4/5) will take some effort, and more so for 1.8(9/5). Meanwhile, are numbers like 3 or 1.5 even possible?

---

As a side note, Geogebra might help you figuring out the construction, but don't expect to find every configuration this way.

Answer 1

A number is constructible in this way iff:

• It's rational, and can be factored into $\prod p_i^{a_i}$ such that:
• $p_i$ are primes, $a_i$ are integers (may be negative, but keep reading)
• If $p_i = 2$, then $a_i \geq -1$
• If $p_i = 4k + 1$ for some integer $k$, then $a_i$ can be any integer
• If $p_i = 4k + 3$, then $a_i \geq 0$ and $a_i$ must be even

Examples:

This means that 1/2, 5/2, 4/5 are okay, while 1/4, 2/3 are not.

Since phenomist already got most of the answer right, I will not duplicate it here. However, there is a probably important part phenomist missed:

The numbers that can be written as $p^2 + q^2$ are those with prime factors $4k + 1$ or $2$. However, since we need $p$ and $q$ to be coprime, only at most one $2$ is allowed.

The general idea from now on is to write an integer, $x$, as the product of gaussian primes. A gaussian integer is a complex number with integer real and imaginary parts. A gaussian prime is one that cannot be written as the product of two non-$\pm 1$, non-$\pm i$ integers. As a corollary of the $p^2 + q^2 = 4k + 1$, each $4k + 1$ prime has 4 ways to be written as two conjugate gaussian primes
  ($(p+qi)(p-qi), ~ (p-qi)(p+qi), ~ (q+pi)(q-pi), ~ (q-pi)(q+pi)$).
$2$ has two ways: $(1+i)(1-i)$ and $(1-i)(1+i)$.

Now suppose $x = p^2 + q^2$. That is equivalent to saying that $x = (p+qi)(p-qi)$. Therefore, we can take both halves of each (real) prime's conjugate factors, put one in $p+qi$, and the other in $p-qi$. And by the way, any powers of $4k + 3$ primes are outlawed; they can't make $p$ $q$ coprime.

But we don't want $p$ and $q$ to share factors. Suppose $p+qi = c(m+ni)$, where $c$ is real. Factor $c$. Since we shouldn't find real factors in each gaussian prime, so it must be the case that $c$ came from one of the following:

  $(u + vi)(u - vi)$
  $(u + vi)(v + ui)$

In other words, $m$ cannot co-exist with $\bar m$ or $i \bar m$. For $s = 4k +1$ prime powers, this is not a problem; just use the form $(p_s + q_s i)(p_s - q_s i)$ only and not the others, and put $p_s + q_s i$ into $p + qi$, and $p_s - q_s i$ into $p - qi$ and it's safe because $p_s$ and $q_s$ are not going to be the same. Not so safe for 2. $1 + i$ can co-exist with neither $1 - i$ nor another $1 + i$. This means that once you have more than one $2$ to factor, you are not going to make it work.

After that, we have a somewhat boring part that combines everything we've deduced into a unified conclusion, as shown in first spoiler:

For $n^2 \over p^2 + q^2$, we can, from 1, add in even powers of any prime, and take away any powers of $4k + 1$ primes and at most one $2$. Therefore:

• For $2$, we can add powers of $0$, $2$, $4$..., and may take or not take $1$.
  Therefore, its power should be anything not less than $-1$.
• For $4k+1$ primes, we can basically add and take anything, so any integer prime is fine.
• For $4k+3$ primes, we can only add even powers, so the power should be non-negative and even.

Answer 2

Clearly, the segments that we draw must form two parallel lines in order to bound a square. Let us consider one set of these parallel lines. Since their endpoints are on integer coordinates, they can be expressed as $ax+by=c$ and $ax+by=d$ for integer $a,b,c,d$, where $a,b$ are coprime. The distance between these two lines can be computed to be $\frac{|c-d|}{\sqrt{a^2+b^2}}$. Since the other pair of parallel lines must be equally spaced (for a square), the total area of the square is therefore $\frac{(c-d)^2}{a^2+b^2}$.
.
Now, let us now characterize all numbers that can be expressed of this form. In particular, the set of numbers that can be expressed in the form of $a^2+b^2$ (for $a,b$ coprime) is precisely those numbers which only have prime factors that are 1 mod 4, and 2. This result is due to Fermat. (We can multiply two expressible numbers using the identity $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$). Therefore, numbers like $1.5 = \frac{3}{2}$ and $3$ cannot be areas of squares that we construct from this method, since $3$ has one prime factor that is 3 mod 4.
.
To show that we can get everything of the form $\frac{n^2}{a^2+b^2}$, it suffices to find integers such that $ax+by=1$ for coprime $a,b$, which we can find via Bezout. Then scale upward by a factor of $n$ to get our result.

Example

$4/5 = \frac{2^2}{1^2+2^2}$, so we need to find $x,y$ such that $x+2y=2$. For instance, $(0,1)$ and $(2,0)$. We also need $x+2y=0$, for instance $(2,-1)$ and $(-2,1)$. Now we do the same for perpendicular lines $-2x+y=-2$ and $-2x+y=0$. For instance, $(0,-2)$ and $(2,2)$ and $(0,0)$, $(1,2)$ respectively. If some segments aren't long enough, you can extend them as needed. We can verify that this gives us the desired area.