Generalize to a graph-theoretic formulation

This may turn out to be not as much a "proof strategy" as "another interesting way of thinking about the problem", but the hope is to generate examples much more tractable by hand and by computer which reveal graph theoretic properties that force certain discrepancies; and translate those into number theoretic properties we can search for (perhaps very rare ones, but ones we can prove exist nonetheless).

---

(General formulation) Define a set of nodes [math]\displaystyle{ a_1, a_2, ... }[/math] with k sets of directed edges [math]\displaystyle{ e_{1}^j, e_{2}^j, ... }[/math] (for [math]\displaystyle{ 1 \leq j \leq k }[/math]) such that each set of edges (with corresponding nodes) forms an acyclic path.

Give each node a value of 1 or -1. Consider any traversal corresponding to a set [math]\displaystyle{ e_{1}^j, e_{2}^j, ... }[/math] that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be [math]\displaystyle{ t_j }[/math].

Possible conditions given a set of nodes [math]\displaystyle{ a_1, a_2, ..., a_n }[/math]:

No subsets (NS): No set of edges is a subset of another set.

Omega set (OS): One labelled set of edges connects [math]\displaystyle{ a_i }[/math] to [math]\displaystyle{ a_i+1 }[/math] for all i from 1 to n-1.

(Needs OS) Always increasing (AI): For any edge from [math]\displaystyle{ a_i }[/math] to [math]\displaystyle{ a_j }[/math], i is less than j.

Isolated roots (IR): Each node can be the root node of only one labelled set of directed edges. [This condition is needed for the definition of completely multiplicative.]

---

Define an infinite set of nodes [math]\displaystyle{ a_1, a_2, ... }[/math] such that given a node [math]\displaystyle{ a_i }[/math] there is a directed edge labelled [math]\displaystyle{ i }[/math] from [math]\displaystyle{ a_i(n) }[/math] to [math]\displaystyle{ a_i(n+1) }[/math] for all [math]\displaystyle{ n \in \mathbb{N} }[/math].

Give each node a value 1 or -1. Consider a traversal starting at a node moving along edges with the same label a finite number of times; then the discrepancy of a given traversal is the absolute value of the sum of all nodes visited. If we only allow traversals to start at the root node of a particular set of labelled edges, asking if it is possible for the discrepancy to be bounded is equivalent to our problem.

The graph doesn’t have to follow the number system. Have a set of nodes (finite or infinite) such that there are labelled directed edges, but allow the edges to be arbitrary.

---

Here is a possible meaning for “completely multiplicative”, although it is extremely messy and could likely be simplified.

Define everything as above, including the 5 extra conditions.

Call the set of edges from condition #1 the omega set, and the root node of that set to be the alpha node.

A node is called prime if the in-degree is 1; that is, the only edge incoming is from the omega set.

A node is a power if the in-degree is 2.

Consider all incoming edges to a particular node; trace the edges backwards to their root nodes. These are the divisors of the node.

Here is a prime factorization algorithm for the node n:

1. List the k divisors of n (excluding the alpha node) [math]\displaystyle{ d_1, d_2, ... d_k }[/math]. Call the path of a divisor to be the traversal going from the divisor to n. Given any divisor a that has divisor b in its path, remove a from the list.

2a. If n is already a power, jump to 2c.

2b. For any divisor that is not prime and is not a power on the list [math]\displaystyle{ d_1, d_2, ... d_k }[/math], connect the divisors of each of [math]\displaystyle{ d_1, d_2, ... d_k }[/math] as a branching tree (again excluding the alpha node); again, given any divisor a that has divisor b in its path, remove a from the list.

2c. For any divisor that is a power on the list [math]\displaystyle{ d_1, d_2, ... d_k }[/math], connect the divisor that is not the alpha node c a multiple number of times m+1, where m is the number of times powers occur in the traversal between the divisor of c and c.

3. Repeat #2a-c until all divisors on the bottom of the tree are prime.

4. The set of divisors at the bottom of the tree is the prime factorization of n.

So, a graph is completely multiplicative if that multiplying the values of all the nodes in the prime factorization of a node n (including repeated nodes as ncessary) gives the value of the node n.

--

Potential questions: Given a discrepancy d, what is a minimal graph (in terms of nodes and/or edges) where the discrepancy is greater than d? What conditions cause the discrepancy to “break”?

Using conditions 1-4, the minimal set of nodes where the discrepancy must be greater than 1 is 4.

Proof: Consider every possible set of edges using 3 nodes.

set A: 1->2->3 set B: 1->3

Then [math]\displaystyle{ a_1 = 1 }[/math], [math]\displaystyle{ a_2= -1 }[/math], [math]\displaystyle{ a_3= -1 }[/math] has a discrepancy of 1.

However, consider these sets with 4 nodes:

set A: 1->2->3->4 set B: 1->3 set C: 1->4

Then no combinations of +1 and -1 (set A constrains the possibilities to + – + -, – + + -, + – - +, and – + – +) avoids having a discrepancy of 2 in some set of edges.