Algorithm for finding multiplicative sequences with bounded discrepancy

To return to the main Polymath5 page, click here.

This is an algorithm for finding long multiplicative sequences over a finite set of complex numbers (eg. {-1,1}), or showing that they don't exist. The algorithm consists of 3 types of operations: Using multiplicativity, using bounded discrepancy, and guessing.

• Using multiplicity is:
  • Setting [math]\displaystyle{ x_1=1 }[/math].
  • Determining one of [math]\displaystyle{ x_a,x_b,x_{ab} }[/math] from the two others using [math]\displaystyle{ x_ax_b=x_{ab} }[/math].
  • Determining one of [math]\displaystyle{ x_a, x_{an^2} }[/math] from the other using [math]\displaystyle{ x_a=x_{an^2} }[/math].

• Using bounded discrepancy is:
  • For any positive integer n, write down all numbers between -C and C with the same parity as n. This is the "possible partial sums at n". If there is only one possible partial sum at n, call it "the partial sum at n".
  • Set 0 to be the partial sum at 0.
  • If we know the partial sum at n-1 and [math]\displaystyle{ x_n }[/math], you may set the partial sum at n to be the sum of these two.
  • If we know the partial sum at n and [math]\displaystyle{ x_n }[/math], you may set the partial sum at n-1 to be the sum at n minus [math]\displaystyle{ x_n }[/math].
  • If neither c-1 or c+1 is a possible partial sum at n, you may delete c as a partial sum at n-1 and n+1.
  • If you know the partial sum at n and at n-1, you may set [math]\displaystyle{ x_n }[/math] to be the sum at n minus the sum at n-1.

• Guessing is:
  • If you can assign a value to [math]\displaystyle{ x_n }[/math] and reach a contradiction (that is one of the formulas in "using multiplicity" is not fulfilled or for some n there is no possible sum at n) using multiplicity, bounded discrepancy, and guessing you may conclude that this is not a possible value for [math]\displaystyle{ x_n }[/math].
  • If there is only one possible value for [math]\displaystyle{ x_n }[/math], you may assign this value to [math]\displaystyle{ x_n }[/math].