Is every integer representable as the sum of four Fibonacci squares?

Question

Lagrange's Four Square Theorem. Every positive integer $N$ can be written as the sum of four squares, i.e.,

$$N = a^2 + b^2 + c^2 + d^2.$$

Zeckendorf's Theorem. Every integer has a unique representation where it can be written as the sum of non-consecutive Fibonacci numbers. i.e.,

$$N = \sum_i F_{c_i}, c_i \in \mathbb{Z}, c_i \ge 2, c_{i+1} \gt c_i + 1,$$

where $F_k$ is the Fibonacci sequence generated by the recurrence equation $F_{n+2} = F_{n+1} + F_n$ with $F_0 = 0, F_1 = 1$.

Question: Is every positive integer also representable as the sum of four Fibonacci squares?

$$ \begin{align} 0 &= F_0^2 \\ 1 &= F_1^2 \\ 2 &= F_1^2 + F_1^2 \\ 3 &= F_1^2 + F_1^2 + F_1^2 \\ 4 &= F_3^2 \\ 5 &= F_3^2 + F_1^2 \\ 6 &= F_3^2 + F_1^2 + F_1^2 \\ 7 &= F_3^2 + F_1^2 + F_1^2 + F_1^2 \\ 8 &= F_3^2 + F_3^2 \\ 9 &= F_4^2 \\ 10 &= F_4^2 + F_1^2 \\ 11 &= F_4^2 + F_1^2 + F_1^2 \\ 12 &= F_4^2 + F_1^2 + F_1^2 + F_1^2 \\ 13 &= F_4^2 + F_3^2 \\ 14 &= F_4^2 + F_3^2 + F_1^2 \\ 15 &= F_4^2 + F_3^2 + F_1^2 + F_1^2 \\ 16 &= F_3^2 + F_3^2 + F_3^2 + F_3^2 \end{align} $$

Note that in the sums above, if we have fewer than $4$ squares, we can always add $F_0^2 = 0^2$ to make it a four square representation.

The sum of four Fibonacci squares representation, if it exists, is not necessarily unique for an integer. e.g.,

$$ \begin{align} 4 &= F_1^2 + F_1^2 + F_1^2 + F_1^2 \\ &= F_3^2 + F_0^2 + F_0^2 + F_0^2 \end{align} $$

Answer 1

If $N$ is big, there are only about $\ln N$ Fibonacci squares below $N$. There are then at most $(\ln N)^4$ different sums below $N$. That count eventually grows more slowly than $N$, so gaps will appear.
I don't know when the first gap will be

Answer 2

Bruteforce gives that first gap is $24$: the only Fibonacci squares less than $24$ are $0, 1, 4, 9$. We need at least two nines (otherwise sum is at most $9 + 3 \cdot 4 = 21$), so now we have to represent $6$ as sum of two numbers from $0,1,4$. But such sum is either $8$, or at most $5$. Thus $24$ isn't sum of $4$ Fibonacci squares.

It is not hard to find representation for numbers from 17 to 23.

(but of course Empy2's argument is much more elegant then this)

Answer 3

By computer search, the possible representations for integers up to 50 are (note, $F_2=1=F_1$ so we only give representations using $F_1$ for brevity) \begin{align} 0 &= F_0^2& 1 &= F_{1}^2\\ 2 &= F_{1}^2+F_{1}^2& 3 &= F_{1}^2+F_{1}^2+F_{1}^2\\ 4 &= F_{3}^2& 4 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{1}^2\\ 5 &= F_{1}^2+F_{3}^2& 6 &= F_{1}^2+F_{1}^2+F_{3}^2\\ 7 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{3}^2& 8 &= F_{3}^2+F_{3}^2\\ 9 &= F_{4}^2& 9 &= F_{1}^2+F_{3}^2+F_{3}^2\\ 10 &= F_{1}^2+F_{4}^2& 10 &= F_{1}^2+F_{1}^2+F_{3}^2+F_{3}^2\\ 11 &= F_{1}^2+F_{1}^2+F_{4}^2& 12 &= F_{3}^2+F_{3}^2+F_{3}^2\\ 12 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{4}^2& 13 &= F_{3}^2+F_{4}^2\\ 13 &= F_{1}^2+F_{3}^2+F_{3}^2+F_{3}^2& 14 &= F_{1}^2+F_{3}^2+F_{4}^2\\ 15 &= F_{1}^2+F_{1}^2+F_{3}^2+F_{4}^2& 16 &= F_{3}^2+F_{3}^2+F_{3}^2+F_{3}^2\\ 17 &= F_{3}^2+F_{3}^2+F_{4}^2& 18 &= F_{4}^2+F_{4}^2\\ 18 &= F_{1}^2+F_{3}^2+F_{3}^2+F_{4}^2& 19 &= F_{1}^2+F_{4}^2+F_{4}^2\\ 20 &= F_{1}^2+F_{1}^2+F_{4}^2+F_{4}^2& 21 &= F_{3}^2+F_{3}^2+F_{3}^2+F_{4}^2\\ 22 &= F_{3}^2+F_{4}^2+F_{4}^2& 23 &= F_{1}^2+F_{3}^2+F_{4}^2+F_{4}^2\\ 25 &= F_{5}^2& 26 &= F_{1}^2+F_{5}^2\\ 26 &= F_{3}^2+F_{3}^2+F_{4}^2+F_{4}^2& 27 &= F_{1}^2+F_{1}^2+F_{5}^2\\ 27 &= F_{4}^2+F_{4}^2+F_{4}^2& 28 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{5}^2\\ 28 &= F_{1}^2+F_{4}^2+F_{4}^2+F_{4}^2& 29 &= F_{3}^2+F_{5}^2\\ 30 &= F_{1}^2+F_{3}^2+F_{5}^2& 31 &= F_{1}^2+F_{1}^2+F_{3}^2+F_{5}^2\\ 31 &= F_{3}^2+F_{4}^2+F_{4}^2+F_{4}^2& 33 &= F_{3}^2+F_{3}^2+F_{5}^2\\ 34 &= F_{4}^2+F_{5}^2& 34 &= F_{1}^2+F_{3}^2+F_{3}^2+F_{5}^2\\ 35 &= F_{1}^2+F_{4}^2+F_{5}^2& 36 &= F_{1}^2+F_{1}^2+F_{4}^2+F_{5}^2\\ 36 &= F_{4}^2+F_{4}^2+F_{4}^2+F_{4}^2& 37 &= F_{3}^2+F_{3}^2+F_{3}^2+F_{5}^2\\ 38 &= F_{3}^2+F_{4}^2+F_{5}^2& 39 &= F_{1}^2+F_{3}^2+F_{4}^2+F_{5}^2\\ 42 &= F_{3}^2+F_{3}^2+F_{4}^2+F_{5}^2& 43 &= F_{4}^2+F_{4}^2+F_{5}^2\\ 44 &= F_{1}^2+F_{4}^2+F_{4}^2+F_{5}^2& 47 &= F_{3}^2+F_{4}^2+F_{4}^2+F_{5}^2\\ 50 &= F_{5}^2+F_{5}^2.& \end{align}

The integers up to $1000$ without such a representation are

24, 32, 40, 41, 45, 46, 48, 49, 53, 56, 57, 61, 62, 71, 80, 85, 87, 88, 92, 95, 96, 101, 103, 104, 105, 106, 108, 109, 110, 111, 112, 113, 116, 117, 119, 120, 121, 122, 124, 125, 126, 127, 131, 134, 135, 140, 142, 143, 144, 145, 147, 148, 149, 150, 151, 152, 155, 156, 158, 159, 160, 161, 163, 164, 165, 166, 167, 168, 176, 184, 185, 189, 190, 197, 200, 205, 206, 208, 209, 210, 211, 213, 214, 215, 216, 218, 221, 222, 224, 225, 226, 227, 229, 230, 231, 232, 236, 239, 240, 245, 247, 248, 249, 250, 252, 253, 254, 255, 257, 260, 261, 263, 264, 265, 266, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 299, 300, 302, 303, 304, 305, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 341, 344, 345, 349, 350, 352, 353, 354, 355, 357, 358, 359, 360, 362, 365, 366, 368, 369, 370, 371, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 404, 405, 407, 408, 409, 410, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 448, 456, 457, 461, 462, 464, 465, 469, 472, 473, 477, 478, 480, 481, 482, 483, 485, 486, 487, 488, 489, 490, 493, 494, 496, 497, 498, 499, 501, 502, 503, 504, 512, 517, 519, 520, 521, 522, 524, 525, 526, 527, 528, 529, 533, 535, 536, 537, 538, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 572, 574, 575, 576, 577, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 613, 616, 617, 621, 622, 624, 625, 626, 627, 629, 630, 631, 632, 634, 637, 638, 640, 641, 642, 643, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 677, 679, 680, 681, 682, 684, 685, 686,687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 781, 782, 784, 785, 786, 787, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 844, 845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 885, 888, 889, 893, 894, 896, 897, 898, 899, 901, 902, 903, 904, 905, 906, 909, 910, 912, 913, 914, 915, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 949, 951, 952, 953, 954, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000

The list of integers up to $1000$ with this representation is shorter:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 42, 43, 44, 47, 50, 51, 52, 54, 55, 58, 59, 60, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84, 86, 89, 90, 91, 93, 94, 97, 98, 99, 100, 102, 107, 114, 115, 118, 123, 128, 129, 130, 132, 133, 136, 137, 138, 139, 141, 146, 153, 154, 157, 162, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 186, 187, 188, 191, 192, 193, 194, 195, 196, 198, 199, 201, 202, 203, 204, 207, 212, 217, 219, 220, 223, 228, 233, 234, 235, 237, 238, 241, 242, 243, 244, 246, 251, 256, 258, 259, 262, 267, 283, 297, 298, 301, 306, 322, 338, 339, 340, 342, 343, 346, 347, 348, 351, 356, 361, 363, 364, 367, 372, 388, 402, 403, 406, 411, 427, 441, 442, 443, 444, 445, 446, 447, 449, 450, 451, 452, 453, 454, 455, 458, 459, 460, 463, 466, 467, 468, 470, 471, 474, 475, 476, 479, 484, 491, 492, 495, 500, 505, 506, 507, 508, 509, 510, 511, 513, 514, 515, 516, 518, 523, 530, 531, 532, 534, 539, 555, 569, 570, 571, 573, 578, 594, 610, 611, 612, 614, 615, 618, 619, 620, 623, 628, 633, 635, 636, 639, 644, 660, 674, 675, 676, 678, 683, 699, 738, 779, 780, 783, 788, 804, 843, 882, 883, 884, 886, 887, 890, 891, 892, 895, 900, 907, 908, 911, 916, 932, 946, 947, 948, 950, 955, 971

This was created by the Scala 3 code below that can probably be improved; it runs in under a second on my computer if you set max = 10000. Click here to run it online in Scastie.

val max = 1000

def fibFrom(n: Int, m: Int): LazyList[Int] =
  n #:: m #:: fibFrom(n + m, n + 2 * m)
val fib = fibFrom(0, 1)

def computeReprs(min: Int, max: Int) = (for
  n <- min to max
  f1 <- fib.takeWhile(f => f * f <= n)
  f2 <- fib.dropWhile(_ < f1).takeWhile(f => f * f <= n - f1 * f1)
  f3 <- fib.dropWhile(_ < f2).takeWhile(f => f * f <= n - f1 * f1 - f2 * f2)
  f4 <- fib
    .dropWhile(_ < f3)
    .takeWhile(f => f * f <= n - f1 * f1 - f2 * f2 - f3 * f3)
  if n == f1 * f1 + f2 * f2 + f3 * f3 + f4 * f4
yield (n +: Seq(f1, f2, f3, f4).map(fib.indexOf(_)))).distinct

val reprs = computeReprs(0, max)

def printForMathSE() =
  def formatRepr(r: Seq[Int]): String =
    if r(0) == 0 then "0 &= F_0^2"
    else
      s"${r(0)} &= " + r.tail
        .filter(_ != 0)
        .map(i => "F_{" + s"$i" + "}^2")
        .mkString("+")

  var counter = 0
  val endMarkerSeq = Seq("\\\\\n", "&  ")
  def endMarker = { counter += 1; endMarkerSeq(counter % 2) }

  extension (reprs: IndexedSeq[String])
    def myMkString(endMarker: => String, acc: Seq[String] = Seq()): String =
      reprs match
        case IndexedSeq()     => acc.mkString
        case IndexedSeq(repr) => (acc :+ repr).mkString
        case IndexedSeq(repr, _*) =>
          reprs.tail.myMkString(endMarker, acc :+ repr :+ endMarker)

  println("\\begin{align}")
  println(reprs.takeWhile(_(0) <= 50).map(formatRepr).myMkString(endMarker))
  println("\\end{align}")

  val partition = (0 to max).partition(k => reprs.exists(r => r(0) == k))
  println(s"integers with repr:${partition(0).mkString(", ")}")
  println(s"integers without repr:${partition(1).mkString(", ")}")
end printForMathSE

printForMathSE()

Answer 4

I've written the bruteforce approach in Mathematica and get results up to $10^9$ in a matter of seconds on my machine. I get $12 553$ distinct integers, in the range from $0$ to $1254718084=4 F_{22}^2$. I did however exclude $F_0 = 0$ from it, because it seemed pointless.

Here's a log plot, where the $x$-axis shows the $n$'th integer and the $y$-axis its value.

fibonacci = Table[Fibonacci[n]^2, {n, 1, 22}];
reverseFib[n_] := 
 SubsuperscriptBox["F", Position[fibonacci, n][[1, 1]] - 1, 2] // 
  DisplayForm
subsets = 
  Tuples[fibonacci, 1]~Join~Tuples[fibonacci, 2]~Join~
   Tuples[fibonacci, 3]~Join~Tuples[fibonacci, 4];
DeleteDuplicates[
  SortBy[{Total[#], Total[reverseFib /@ #]} & /@ subsets, 
   First]] // TableForm

Since the list is way too exhaustive, I uploaded it to pastebin