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; then these properties might also appear in the original number theory version of the problem.

---

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. Then there are interesting questions like; 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”? My hope is we can isolate certain graph theoretic properties which cause the logic to break and translate those into number theoretic properties we can search for (perhaps very rare ones, but ones we can prove exist nonetheless).

---

While it’s fun to think about the completely general version of the structure (for example, cycles of odd degree cause unbounded discrepancy), for the sake of the original problem it might be useful to set some conditions.

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

1. 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.

2. For any edge from [math]\displaystyle{ a_i }[/math] to [math]\displaystyle{ a_j }[/math], i is less than j.

3. Given a set consisting of all labelled edges of a given label, any traversal starting from the root node of the set can traverse the entire set of edges.

4. No set of edges is a subset of another set (this prevents having arbitrary start points).

5. Each node can be the root node of only one labelled set of directed edges.

Given these conditions, 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.

---

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.