math problem (easy), algo problem (dunno if easy)

[DrStraw]

consider the following pic. for there to be an equilateral triangle, the 3rd point can only possibly be in one of six places to make two sides equal.
either down 4 more and either left or right 2, or right or left four and up or down two. all of these fail. in general, you will always have the third side the wrong length. though i don't see an efficient way to prove it.

I just did prove it, in my post above. Also, there are only two other places the third point can be.

[perceval]

Funny how the discussion went in places i did not think about.
My question was, indeed, about integer coordinates, I just put in on a goban because its the thing to do here to interest peoples.
my proof was close the one in the link by RBerenguel, ie using only pythagore theorem and arriving to contradictions on the prime decomposition of a square

indeed the rotation idea is nice because it extends naturally to the rational case

For the algo proposed by HermanHiddema,

You can reduce the complexity to just N² by picking A on the bottom edge, and B on the right edge.
ie A=(0,N-X) B=(N,Y)with X>Y (by symmetry). in that case if the 3rd point of the equilateral trinagle doenst fit on the goban, it wont fit for any translation of the base vector
you can also reduce to the case where , gcd(N-X,Y)=1,( the fixed edge is not reducible) but this doesnt reduce the O(N²) complexity

but there is a small issue
this probably works, but you have no guarantee that the integer point closest to the minimum is the on grid minimum as the derivative of E is not isotrope;
ie if we fix A(N-X,0) and B (N,Y) and let C(N-x,y) vary:

with a= sqrt(X²+Y²)
b(x,y) =sqrt((X-x)²+y²)
c(x,y)=sqrt((x)²+(y-Y)²)

E(x,y)=(a-b(x,y))²+(a-c(x,y))²+(b(x,y)-c(x,y))²/(ab(x,y)c(x,y))^2/3

min E(x,y) is obtained for x_min=(N-X)+X/2-sqrt(3)Y/2,y_min=sqrt(3)X/2+Y/2

and we want the min of E with x,y integer and 0<x<N,0<y<N.

Its not clear in general that the minimum on this set is the closest point to (x_min,y_min).

If the point is in the goban, you need to check the 4 closest points (can we prove its enough ?)
If (x_min, y_min) is outside the goban, its enough to check 2 points on the edge of the goban, so complexity can stay at N², but we would need to prove that the function have only 1 single min on the edge. (probably true)

[DrStraw]

All very nice, Perceval, but it sounds a bit like using a slegehammer to crack a peanut. Good mathematics is simple and elegant. This sounds complex and inelegant as compared to the polar coordinates solution.

[perceval]

All very nice, Perceval, but it sounds a bit like using a slegehammer to crack a peanut. Good mathematics is simple and elegant. This sounds complex and inelegant as compared to the polar coordinates solution.

Agreed, the short proof is the way to go.

The other part is an algorithm, its always much uglier than nice proof. But it answers a slightly different question: what is the closest thing you can get to an equilateral triangle, after proving you can't have a real one ? There is a different kind of beauty in shaving powers of N in an algorithm complexity. Or maybe not a beauty but a cleverness

[DrStraw]

All very nice, Perceval, but it sounds a bit like using a slegehammer to crack a peanut. Good mathematics is simple and elegant. This sounds complex and inelegant as compared to the polar coordinates solution.

Agreed, the short proof is the way to go.

The other part is an algorithm, its always much uglier than nice proof. But it answers a slightly different question: what is the closest thing you can get to an equilateral triangle, after proving you can't have a real one ? There is a different kind of beauty in shaving powers of N in an algorithm complexity. Or maybe not a beauty but a cleverness

I am not really big on algorithms, even though I made a living using them in the IT world before I retired. I even wrote a PhD thesis about using them in algebra almost 40 years ago. But I still don't think the four color problem has been proved. Is has merely been shown to be true.

[drmwc]

Grunching, because I wanted to work it out on my own.

First problem:

One equilateral triangle in the complex plane has vertices at 0, 1 and e^(i*pi/3). (Is there a Latex editor this forum can utilise?) Call this triangle T0 - normal form for an equilateral triangle.

Now suppose we have an arbitrary equilateral triangle, T1, with integer coordinates. Assume WLOG one vertex is at the origin (we can translate to make this true). Suppose one other vertex is at a+bi for some integers a and b.

Now consider the coordinates of the normal form triangle T0 under the transformation f(z)=(a+bi)*z. This mapping is a scaling and a rotation, so it preserves equilateral triangles. One vertex of the transformed triangle is the origin, another is at a+bi. So the third point is either the third vertex of T1 or its reflection in the line from 0 to a+bi. I will assume it's the third vertex - the following argument works if it's the reflection as well.

So the third vertex is at f(e^(pi/3)), which equals e^(i*pi/3)*(a+bi). This equals a/2-b*3^.5/2+i*(b/2+3^.5/2*a).

We know the real and imaginary parts of this are integers (by assumption). The real coordinate tells us that b must be zero (given that a is an integer). If b is non-zero the answer is irrational, let alone an integer. However, then the imaginary part tells that a must also be zero, which is a contradiction as required. (If a=b=0, then T1 wasn't actually a triangle).

I have some thoughts on the second problem I'll post later.

EDIT: Now I've read the thread, my solution and Dr Straw's are the same but expressed differently. I ignored the fact a goban is rectangular rather than square, but as others noted, if the ratio is rational the proof is unaffected.

[drmwc]

Second problem:

I think it can be done in around O(n^4). The algorithm is this:

1) Work out 3^0.5/2 to sufficient accuracy. This a bit wooly, but I think this stage is O(n) or O(n^2).
2) Consider all lines, where one vertex is at the axis and the other is at a+bi, with a and b positive and less than or equal to n. This step is O(n^2). We don't need negative mumbers since they will give the same answer.
3) For a give a+bi, work out the coordinates of the point making an equilateral triangle using the approximation at step 1 and the formula from my previous post.
4) Find the 4 (say - 6 may actually be needed) integer points nearest the equilateral point found at point 3.
HYPOTHESIS: One of these 4 points mimimises the triangle metric given the base line. I haven't actually proved this, since I'm lazy, but it feels intuitively plausible. This is quick.
5) We now have 4 triangles whose metric we should assess. Run over them in turn. See if any of them are scale multiples of earlier triangles checked. If they are, dsiscard them (we already know the metric). I think this step is O(n^2).
6) Find the metric for the triangle considered. I'm not sure of the comlexity of this step, but O(n^2) sounds like a good guess.

So overall, the number of lines is O(n^2) and we do a calc of complexity around O(n^2) fpr each point. So this seems to be around O(n^4). The key missing bit is proving my hyothesis.

EDIT: This is the same as Perceval's revised estimate of the complexity. The difference is that I've allowed for evaluating the triangle metrix to sufficient accuracy, which I think must have non-zero cost.