{
  "$type": "site.standard.document",
  "description": "Villanova Summer REU",
  "path": "/posts/algorithms/",
  "publishedAt": "2024-12-09T00:18:33.000Z",
  "site": "at://did:plc:6n2ngs7zpcpwxz3jaoxj56tu/site.standard.publication/3mo6y7ludvn2h",
  "tags": [
    "math",
    "research",
    "website"
  ],
  "textContent": "So it was a fine summer morning.\nOur research team was about to start our project \"Counting Arithmetical Structures on Cycles with a Doubled Edge\".\nFrom the description of the project it is immediately obvious that this kind of counting can be done by brute force, and me being the only computer scientist in my group of mathematicians I start coding up a couple algorithms for this.\n\nGiven the fact this article's thesis isn't arithmetical structures or combinatorics, you can read more about those here:\n- arithmetical structures\n- cycle graphs\n- doubled edge cycle graph\n- divisibility\n\nWe'll start simple.\n\nWhat is a graph?\n\nHere we see a couple graphs, some of them have shapes that are so recognizable that they're given names.\n- The complete graph has every vertex connected to every other vertex.\n- The bident graph has two vertices on one side and a path graph coming out the other end.\n- The star graph has a vertex in the center connected to every other vertex, the other vertices must not be connected.\n- The cycle graph just forms a big ol' cycle.\nGraphs are super common and I feel like the Wikipedia page for it does a great job of explaining this!\n\nIn this case, we were looking at doubled edge cycles:\n\nIt's literally just a cycle graph and you add an extra edge between two vertices.\nAdditionally, the set of cycle graphs is usually denoted as \\(C(n)\\) where \\(n\\) is the amount of vertices.\nThen, the set of doubled edge cycles is denoted as \\(C^\\sim(n)\\).\n\nWhat is an arithmetical structure?\n\n1. You take a graph and you put integers on each vertex.\n2. If the number at the vertex divides the sum of its neigboring vertex, then it's an arithmetical structure.\n\nTechnically, you also need an extra condition but this is the gist.\n\nLet's see an example.\n\nWe have a graph with four vertices: 1, 1, 2, 3.\nLet's verify if each vertex divides the sum of its neighbors:\n- Vertex 1 (top):\n    - This vertex is connected to vertex 1 (left) and vertex 2 (right).\n    - Does 1 divide 1 + 2? Yes!\n- Vertex 1 (left):\n    - This vertex is connected to vertex 1 (top) and vertex 3 (bottom).\n    - Does 1 divide 1 + 3? Yes!\n- Vertex 2 (right):\n    - This vertex is connected to vertex 1 (top) and vertex 3 (bottom).\n    - Does 2 divide 1 + 3? Yes!\n- Vertex 3 (bottom):\n    - This vertex is connected to vertex 1 (left) and vertex 2 (right).\n    - Does 3 divide 1 + 2? Yes!\n\nWe checked the divisibility condition for all the vertices and we have confirmed:\nThis is an arithmetical structure\n\nRemarks\n- The extra property that I skipped is the fact that the GCD of all vertices must be 1.\n- Lorenzini in 1989 proved that, for all finite connected graphs there exist finitely many arithmetical structures:\n    - Lemma 1.6\n\nArmed with this knowledge, it is pretty obvious that we can just brute force all the possible combination of numbers on each vertex and just check if the divisibility conditions are met.\n\nLet's code!\n\nBrute Force Search\nFor example, for \\(C^\\sim(3)\\) we have a weird pizza shaped thing:\n\nIf we label the top two vertices \"a\" and \"b\" and the bottom vertex \"c\" we can say that a valid arithmetical structure meets the following criteria (in Python):\n\nThree of these properties have to do with divisibility, so let's group them and\npop them into a function:\n\nand iterate over all possible values:\n\nThis will print all of the valid arithmetical structures on \\(C^\\sim(3)\\) with vertex values under 1000.\n\nNow if we wanted to do this for \\(C^\\sim(6)\\) . . .\n\nYup, this is it . . .\nLooks great doesn't it ?\n\nThis doesn't actually run on the compute server we host our jupyter notebooks on so I had to transpile this to C++ to even be able to compute anything.\n\nIt has a complexity of  where  is the upper bound and  is the degree of the doubled edge cycle.\nAdditionally, I will save you the horrors of looking at the C++ version of all of this . . . (for now)\n\nThe C++ version took 5 days to output all of the structures for \\(C^\\sim(8)\\) . . .\n\nOptimizations\n\nI won't get into the details, but it turns out that we only need to vary the two vertices that share the doubled edge.\nThe rest of the vertices on the graph can be constructed from those two.\nFor simplicity let's just say that we have a function  that will return the rest of the doubled edge cycle.\n\nThe function goes a little like this (in C++):\n\nC++ modulus doesn't compute negative modulus correctly so I had to implement that myself with:\n\nThis means the search space went from  to just !\nNow we need to iterate over every pair of two numbers from 1 to the upper bound and check if we can merge them at the start.\n\nFirst of all, we want to find the total count for",
  "title": "Algorithms"
}