Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I asked a question yesterday regarding numbers defined on graph structures that I call graph numbers. I posted the algorithm I was using to define graph numbers, which are simply a natural extension of linear numbers we use all the time. Nolion's response was close but not quite right. The equations are actually:

$$d_{m+n}(v) = \biggl (d_{n}(v) + d_{m}(v) + \sum_{(u,v)\in{E}}{d_{{m+n},{carry over}}(u)} \biggr ) \mod {2}$$

$$d_{{m+n},carryover}(v) = \biggl \lfloor \frac {d_{n}(v) + d_{m}(v) + \sum_{(u,v)\in{E}}{d_{{m+n},{carry over}}(u)} } {2} \biggr \rfloor$$

After reading nolion's response, I was able to come up with these equations. Notice, they are added in $Z$, which is why I need the $\mod 2$ to bring them back to $Z/2Z$. However, the digits of m and n are chosen from $Z/2Z$ (just as in normal binary addition of more than 2 numbers). But the order of evaluation of $d_{m+n}$ matters (which, again, I am not sure how to describe mathematically) starting from the "root" nodes and evaluating as in a Breadth First Search. Notice, that if the Directed Acyclic Graph is a linear connection of nodes, this becomes normal arithmetic in base 2. My question is, has there been any work done on such numbers?

share|cite|improve this question
I just need to know if I can take this to my professor without looking like an idiot. Any help would be greatly appreciated. I am a Computer Science grad student, and if no work has been done in this area, I am considering doing my thesis on this. – user7263 Feb 19 '11 at 21:36
Thanks for clarifying the question somewhat. In yesterday's question you also wrote that you defined multiplication on these numbers -- how is that defined? – joriki Feb 19 '11 at 21:37
That gets really complicated. For the subset of numbers that are isomorphic to the regular integers over addition, you can convert them to integers, multiply, and convert them back to these graph numbers. For those numbers that are not part of that subset, I have developed a process for specific types of graphs (square, cubic, etc..., and polyhedral, triangular, square, pentagonal, etc... and similar types of graphs), but again, I don't know how to describe it mathematically, because it requires "shifting" the graph. – user7263 Feb 19 '11 at 21:44
@Fred: I neither gave nor few any conclusions; in fact, what I said is that you cannot make conclusions as to the usefulness of something based only on the fact that it is new. Your (undisclosed) definition of "useful" is at odds with the way the vast majority of the world uses that word, and I'll wager it is at odds with the way 100% of Computer Science people use the word. And since you say you are in Computer Science, and are thinking about this for a dissertation, then it is the CS-notion of "useful" that is at issue. (cont...) – Arturo Magidin Feb 19 '11 at 22:52
@Fred: I'll wager that none of the many ways in which CS people use the word "useful" is as a synonym for "nobody has done it before", which is how you are proposing to use it. And numbers are considered useful not because of the many thing you can do that have no practical applications, but in spite of those, and because of all the ways that they do have practical applications. Just because the sky is blue doesn't mean that everything which is above your head is blue. – Arturo Magidin Feb 19 '11 at 23:30
up vote 0 down vote accepted

I had a nice, long answer written out that has been subsumed by all the comments above. Oh well.

The only part that isn't redundant is that for multiplication, you want to look at whether the set of endomorphisms of your DAG acts vertex transitively. Ideally, it would act simply vertex-transitively, because otherwise, you would have to include choices of endomorphisms explicitly in the structure. Anyway, that's the mathematical terminology for your "fractal structure".

share|cite|improve this answer
I think I understand you. I have "shown" that for certain graphs, multiplication is transitive and vertex transitive on these graph numbers. It is also commutative, and distributive over addition. – user7263 Feb 19 '11 at 22:19
Now, I am going to take (what some would consider) an enormous leap. I would say that these numbers (or, the lack thereof) are the reason why Fermat's Last Theorem and Fermat's Polygonal Number theorem are so difficult to solve. You can describe "cubic" or high powers with these numbers, but in a different form. You can also describe polygonal numbers. And Fermat was specifically investigating these types of numbers and claimed he had a proof for his (also considered Cauchy's) Polygonal Number Theorem. Now, I don't put much weight on this line of reasoning, but it does make some sense. – user7263 Feb 19 '11 at 23:39
@Aubrey da Cunha: Can you point me toward the work that has been done for addition? Thanks. – user7263 Feb 20 '11 at 0:03
I'm not sure exactly what work you mean. As far as I know, nobody has defined exactly this structure before. Under appropriate assumptions about the underlying graph, you shouldn't have any trouble showing that these things form a ring, but math is awash with examples of rings. Arturo's comment about the usefulness of these rings boils down to an explanation of why anyone should care about these rings. Maybe they have interesting computational properties? – Aubrey da Cunha Feb 20 '11 at 7:08
@Fred I should add that I agree with Arturo's assessment: do show this to your professor and don't sweat the response too much. – Aubrey da Cunha Feb 20 '11 at 7:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.