# Computer proof that completely multiplicative sequences have discrepancy greater than 2

From Polymath Wiki

The following |C code implements this algorithm for making deductions about multiplicative functions of discrepancy 2. At any given time, the "knowledge" that this algorithm has is given by:

- a reduced expression for f(n) for each n, of the form f(n) = +f(m) or f(n)=-f(m). Thus for instance if we know that f(2)=-1, then we can reduce f(12)=-f(3). This is recorded by an array vals, thus for instance vals[12]=-3 would be recording the fact that f(12)=-f(3).

- Upper and lower bounds for each of the partial sums f[1,n] := f(1)+...+f(n).

The "easy" deductions that the algorithm makes automatically are:

- consequences of multiplicativity (e.g. f(n^2)=1);
- Adjusting upper and lower bounds for f[1,n] based on knowledge of f[1,n-1] and f(n), or of f[1,n+1] and f(n+1);
- Deducing the value of f(n) given enough information about f[1,n] and f[1,n-1]

After running the initialisation routine init(), there are three main routines:

- set(p,s): this forces f(p)=s
- deduce(): run all the easy deductions available from the current state of knowledge; halt if an error occurs and display the current state
- display(): display the current state.