MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 fixed another factor of two error

This is building off of the work of Richard Borherds' answer and the comment I made there. We can provide a way to compute an upper bound which would be much better than the current exponential bound in $n$, but relies on enumerating solutions to certain Diophantine equations.

We are going to try and enumerate the distinct values of the expression $$e_11^n+e_22^n+\cdots+e_kk^n,$$ where $e_i = \pm 1$ for $i \in [1,n]$. Let $S$ be the set of all values attained by this expression. We have obviously $|S| \le 2^k$ as there are $2^k$ ways to choose the signs, but we know that two different choices for the $e_i$ may give the same numeric value. An illustrative example occurs in case $(k,n) = (5,2)$, where we have $$+1^2+2^2+3^2+4^2-5^2 = +1^2+2^2-3^2-4^2+5^2 = 5.$$ If we have two choices for the $e_i$ - for now, call the two lists of coefficients $a_i$ and $b_i$ that coincide, we may form sets $A = \{i \in [1,n]: a_i = +1, b_i = -1\}$ and $B = \{i \in [1,n]: a_i = -1, b_i = +1 \}$. Then we know that $A \cap B = \emptyset$, and more importantly, $\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Now define a function $s(k,n,a,b)$, with $a \ge b$ and $a+b \le k$, to count the number of pairs of sets $(A,B)$ satisfying the following conditions:

  • $A \cup B \subseteq [1,k]$;
  • $A \cap B = \emptyset$;
  • $|A| = a$ and $|B| = b$;
  • if $a = b$, then $\max{A} < \max{B}$;
  • $\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Then we may write $$|S| \ge 2^k - \sum_{m=3}^k2^{k-m}\sum_{1 sum_{m=3}^k2^{k-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j).$$ Indeed, we see that any two if some set of choices of $e_i$ which give the same numerical valuewill be removed completely (that is, both choices of $e_i$ all but one will be removed ) by this inclusion-exclusion counting. We may simplify this a bit further by writing $$f(k,n) = \sum_{m=3}^k2^-m\sum_{1 sum_{m=3}^k2^{-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j)$$ as our equation then becomes $|S| \ge 2^k(1-f(k,n))$. Now once we have established suitable bounds on $f(k,n)$, we may proceed as Richard did, noting that we simply solve for the least valid value of $2^k(1-f(k,n)) k$ in the inequality $$2^k(1-f(k,n)) \ge \sum_{i=1}^ki^n$ for $k$.2\sum_{i=1}^ki^n.$$

Where does Fermat's Last Theorem come in? Well, in case $n \ge 3$, we need only sum from $m = 4$ to $k$ - there are no solutions for $m = 3$, as a solution for $m = 3$ takes the form $x^n + y^n = z^n$! So we lose what is (possibly?) the largest contributing term to $f(k)$.

Note

EDIT: I think I may be was off by a factor of twoor so in my definition of $f(k,n)$ and in the removing of over-counts: I will come back and edit this once I've convinced myself of what I'm doing. The form posted is correct, although there are definitely some problems with the finish of the problem - in particular, if $a(n) = k$, then we should have two expressions equal to zero, both of which get deleted!Darn.
show/hide this revision's text 1

This is building off of the work of Richard Borherds' answer and the comment I made there. We can provide a way to compute an upper bound which would be much better than the current exponential bound in $n$, but relies on enumerating solutions to certain Diophantine equations.

We are going to try and enumerate the distinct values of the expression $$e_11^n+e_22^n+\cdots+e_kk^n,$$ where $e_i = \pm 1$ for $i \in [1,n]$. Let $S$ be the set of all values attained by this expression. We have obviously $|S| \le 2^k$ as there are $2^k$ ways to choose the signs, but we know that two different choices for the $e_i$ may give the same numeric value. An illustrative example occurs in case $(k,n) = (5,2)$, where we have $$+1^2+2^2+3^2+4^2-5^2 = +1^2+2^2-3^2-4^2+5^2 = 5.$$ If we have two choices for the $e_i$ - for now, call the two lists of coefficients $a_i$ and $b_i$ that coincide, we may form sets $A = \{i \in [1,n]: a_i = +1, b_i = -1\}$ and $B = \{i \in [1,n]: a_i = -1, b_i = +1 \}$. Then we know that $A \cap B = \emptyset$, and more importantly, $\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Now define a function $s(k,n,a,b)$, with $a \ge b$ and $a+b \le k$, to count the number of pairs of sets $(A,B)$ satisfying the following conditions:

  • $A \cup B \subseteq [1,k]$;
  • $A \cap B = \emptyset$;
  • $|A| = a$ and $|B| = b$;
  • if $a = b$, then $\max{A} < \max{B}$;
  • $\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Then we may write $$|S| \ge 2^k - \sum_{m=3}^k2^{k-m}\sum_{1 \le j \le m/2}s(k,n,m-j,j).$$ Indeed, we see that any two choices of $e_i$ which give the same numerical value will be removed completely (that is, both choices of $e_i$ will be removed) by this inclusion-exclusion counting. We may simplify this a bit further by writing $$f(k,n) = \sum_{m=3}^k2^-m\sum_{1 \le j \le m/2}s(k,n,m-j,j)$$ as our equation then becomes $|S| \ge 2^k(1-f(k,n))$. Now once we have established suitable bounds on $f(k,n)$, we may proceed as Richard did, noting that we simply solve $2^k(1-f(k,n)) \ge \sum_{i=1}^ki^n$ for $k$.

Where does Fermat's Last Theorem come in? Well, in case $n \ge 3$, we need only sum from $m = 4$ to $k$ - there are no solutions for $m = 3$, as a solution for $m = 3$ takes the form $x^n + y^n = z^n$! So we lose what is (possibly?) the largest contributing term to $f(k)$.

Note: I think I may be off by a factor of two or so in my definition of $f(k,n)$ and in the removing of over-counts: I will come back and edit this once I've convinced myself of what I'm doing. The form posted is correct, although there are definitely some problems with the finish of the problem - in particular, if $a(n) = k$, then we should have two expressions equal to zero, both of which get deleted!