Let $b = 4m$ and $a = b - z$ for convenience, note that $z \le 2m$. Suppose $a^2 + b^2 - ab = k^2 \implies k^2 - (b-a)^2 = ab \implies (k+z)(k-z) = ab$. Since the RHS has $v_2$ exactly $2^n$, and since at most one of the factors on the LHS is divisible by $4$, we have two cases. Case 1: $4 \nmid k+z$ In this case, we have $k-z = 2ml$ for some integer $l$. So $(2ml)(2ml+2z) = 4ma \implies l(ml+z) = a \le b = 4m \implies l^2 < 4 \implies l = 1$. So $m + z = a \implies 4m + 4z = 4a \implies b + 4(b-a) = 4a \implies 8a = 5b$, not possible since $v_2(b) = 2^n > 3$. $\square$. Case 2: $4 \nmid k-z$ In this case, $k + z = 2ml$ so $2ml(2ml-2z) = 4ma \implies l(ml-z) = a \implies ml^2 = a + lz \le 4m + 2ml \implies l^2 \le 4 + 2l$ so $l \le 3$. We can just check these now. $a = ml^2 - zl \implies 4a = bl^2 - (b-a)l \implies (4+l)a = bl(l-1)$. So $l = 1$ is impossible. $l = 2 \implies 6a = 2b$, not possible again. $l = 3 \implies 7a = 6b$, impossible. $\square$. We have exhausted all possible cases and so $a^2 + b^2 - ab$ is indeed never a square. $\blacksquare$

Let $$k^2 = a^2 + b^2 - ab \qquad (1)$$Observe that $2^{2^n-1} = \frac{b}{2} < a < k < b = 2^{2^n}$. Write $(1)$ as $b(b-a) = (k+a)(k-a)$. Since $\gcd(k+a, k-a) = \gcd(k+a, 2a)$, $k+a, k-a$ cannot both have any common factors with $b$ except for $2$, so we see that $\frac{b}{2} \mid k+a$ or $\frac{b}{2} \mid k-a$. In the first case $k+a = t \cdot \frac{b}{2}$, but for size reasons, $t = 2$ or $t = 3$ (more specifically, $ 1 \cdot \frac{b}{2} < k+a < 2b = 4 \cdot \frac{b}{2}$. If $t = 2$ then $k+a = 2 \cdot \frac{b}{2} = b$, so $k = b-a$, but observe that this means, by $(1)$ that $a^2 + b^2 - 2ab = a^2 + b^2 - ab$, impossible. Now suppose $t = 3$. Then $k + a = 3 \cdot \frac{b}{2} \implies k = \frac{3b-2a}{2}$. Again, plugging this in $(1)$ gives $9b^2 + 4a^2 - 12ab = 4a^2 + 4b^2 - 4ab \implies 5b^2 = 8ab \implies 5b = 8a \implies \nu_2(b) = 3$, since $a$ was odd, contradiction. Now we check $\frac{b}{2} \mid k-a$. Once again let $k-a = t \cdot \frac{b}{2}$, but now see that since $\frac{b}{2} < a < k < b$, it is impossible for $k-a$ to be a multiple of $\frac{b}{2}$ since it has to be less than $\frac{b}{2}$. We are done.

Ummm...pretty straightforward. Let, FTSOC , $b^2+a^2-ab=k^2 \implies b(b-a)=(k+a)(k-a)$ Now one of the two factors on the right will have to have $v_2 \leq 1$, so $\textbf{Case 1)} k-a=2^{2^n-1}.x$ and $k+a =2\frac{b-a}{x} \leq \frac{b}{x}$ because of the given bounds. If $x>1$ , then $k\leq \frac{b}{2}-a \leq0$.So $x=1$.Then $k=a+\frac{b}{2}=2b-3a \implies a=\frac{3b}{8} \implies 2^n \leq 3 $ .The two cases $n=1$ and $n=0$ and be checked manually to get contradictions in both case. $\textbf{Case 2)}k+a=2^{2^n-1}.x=\frac{bx}{2}$ and $k-a =2\frac{b-a}{x} \leq \frac{b}{x}$Solving , we get that $$b\geq a=\frac{bx^2-4(b-a)}{4x} \geq \frac{b(x^2-2)}{4x} \implies x^2-4x-2 \leq 0 \implies x \leq 4$$.The two cases for $x=1$ and $x=3$ can be checked manually again.

I think my solution is somehow new in the thread , Just bounding and some divisibility argument suffices to solve the problem - First note that $$(a-b)^{2} < a^{2} + b^{2} - ab < (a - b + 2b)^{2}$$, so FTSOC assume that $$ a^{2} + b^{2} - ab = (a-b+x)^{2}$$, for some $0 < x < 2b$. Now expanding we get the above expression is equivalent to $$ab = x(x +2a - 2b)$$, first note that $a$ is odd and $b$ is even , we get $x$ is even , so let $x = 2k$ , for some integer $k$. Now note that this is equivalent to $$ab = 4k(k +a - b)$$. We will make some cases - Case -1 $k$ is even. In this note that $k+a-b$ will be odd so $v_{2} (LHS) = 2^{n} = 2 + v_{2}(k)$ , implying $v_{2} (k) = 2^{n} - 2$ , so $k = 2^{2^{n} - 2}. t = \frac{bt}{4}$ , for some odd $t$ , implying $x = 2k = \frac{bt}{2} <2b$ , implying $t = 1$ or $3$ , which can be manually removed. Case- b $k$ is odd In this we have $v_{2} (k+a -b) = 2^{n} - 2$ , so again by same argument again and using $a \le b \le 2a$ , we get this is possible only when $a = \frac{5b}{8}$ , or $a= \frac{21b}{16}$ , which is note possible as first implies $a$ is even , while the second implies $b = 2^{2^{2}}$ , which is again impossible, So summing all the above we get an contradiction. Hence we are done $\blacksquare$

This problem was so nice! Wish we get something nice like this on day 2. Let $a^2-ab+b^2=x^2\implies b^2-ab=(x-a)(x+a).$ Also, $x$ is odd. Also $\max(v_2(x-a),v_2(x+a))=2^{2^{n}-1}$ as ($\gcd(x-a,x+a)=2a$). Note that $$a^2<a^2-ab+b^2<a^2-a\cdot a+(2a)^2=4a^2.$$So $a<x<2a.$ If $v_2(x-a)=2^{2^n-1},$ then $x-a=(2^{2^n-1})k.$ So $$x-a=\frac{bk}{2}\implies 2x-2a=bk.$$But $4b>4a>2x,~~2a>b.$ So $2x-2a<4b-b=3b \implies k=1,2.$ But $$v_2(x-a)=2^{2^n-1}\implies k=1\implies x-a=b.$$So $$a^2-ab+b^2=(a+b)^2\implies 2ab=-ab$$which is absurd. Hence $$v_2(a+x)=2^{2^n-1}\implies 2x+2a=bk<6b\implies k=1,3,5.$$ Case 1: $2x+2a=b$ So $$ x=\frac{b-2a}{2}\implies 4a^2-4ab+4b^2=(2a-b)^2$$$$\implies 4a^2-4ab+4b^2=4a^2-4ab+b^2\implies b=0$$NP. Case 2: $2x+2a=3b$ As $n>2, b=8b'.$ So $$x=\frac{3b-2a}{2}\implies 5b^2-8ab=0 \implies 5b-8a=0 \implies 5b'-a=0$$NP as $5b'$ is even. Case 3: $2x+2a=5b$ As $n>2,$ let $b=16b'$ So $$ x=\frac{5b-2b}{2}\implies 21b-16a=0\implies 21b'-a=0$$which is not possible as $b'$ is even. So there are no positive integer solutions to $a^2-ab+b^2=x^2.$

Suppose $a^2+b^2-ab = k^2 \implies b^2-ab = (k-a)(k+a).$ Note $v_2(b^2-ab) = 2^n.$ Since $a$ and $k$ are odd, one of $k-a,k+a$ is a multiple of $2$ but not $4,$ so the other is a multiple of $2^{2^n-1}$ but not $2^{2^n}.$ Case 1: $k-a = \frac{b}{2} j$ for an odd integer $j.$ So $$k+a = \frac{2(b-a)}{j} \implies k = \frac{2(b-a)}{j} - a < \frac{b}{j} - \frac{b}{2}$$and if $j > 2$ then $k < 0$ which is contradiction. So $j = 1 \implies k = \frac{b}{2} + a.$ Plugging into $a^2+b^2-ab = k^2$ yields $a = \frac{3}{8}b.$ But this means $a$ is even. Case 2: $k+a = \frac{b}{2} j$ for an odd integer $j.$ Note the very silly bound $\frac{b}{2} < a < k+a < b + b < \frac{5b}{2}$ so $j=3$ and $k = \frac{3b}{2} - a.$ Plugging into $a^2+b^2-ab = k^2$ yields $a = \frac{5}{8}b.$ Again this means $a$ is even. $\square$

Perhaps mods weren’t attentive enough to look at the thread history, but this was an original solution that I wrote. Therefore I don’t know why it got deleted. Note $a^2+b^2-ab=(a-b)^2+ab$. Now it is left to prove that $ab$ is not of the form $2k+1$ for nonnegative integers $k$. This is clearly true because $b$ is even and $a$ is odd. $\blacksquare$

Geometry285 wrote: Note $a^2+b^2-ab=(a-b)^2+ab$. Now it is left to prove that $ab$ is not of the form $2k+1$ for nonnegative integers $k$. I do not understand this. For example, what if $(a-b)^2=1$ and $ab=8$? (I know this doesn't work but you do not consider this?)

Hopefully didn't mess up. Let $a^2 + b^2 -ab = (a+x)^2 \iff b(b-a) = x(x+2a)$. Note that $x$ is even, now we perform casework on 2-adic evaluation of $x$. Case 1: $\nu_2(x) \ge 2$. Comparing $\nu_2$ on both sides yield $2^n = \nu_2(x) + 1 \implies x = 2^{2^n - 1}c$ where $c$ is odd, substitute everything back in $$2^{2^n} - a = c(2^{2^n - 2}c + a) > c^2 2^{2^n -2} \iff c^2 <4 \iff c=1$$then solving yields $a$ is even which is a contradiction. ~~Ignore the edge cases when n is smol~~ Case 2: $\nu_2(x)=1$. Let $x=2c$ where $c$ is odd. Substitute everything back in $$2^{2^n-2}(b-a)=c(c+a) \implies c+a=2^{2^n-2}\ell$$where $\ell$ is odd. So $b-a = c\ell \le a \iff \ell (2^{2^n-2}\ell -a) \le a$, further solving $$\iff \dfrac{2^{2^n -2}\ell ^2}{\ell + 1} \le a \le b = 2^{2^n} \iff \ell \le 2 \iff \ell = 1$$then solving yields $a = b-c \iff 2a = 2b - 2c \iff (a + x)^2 = (2b - a)^2 =a^2 + b^2 -ab \iff a=b$ but $b$ is even while $a$ is not, so done.