Thoughts on FunSearch's program to construct a large independent set in the
fifth strong power of C7

We don't improve on their results, just some thoughts. However, we do remove a
line from the program to simplify it, without changing its effectiveness.
====== 
Background: 
FunSearch was a paper/project from DeepMind in December 2023 to use LLMs to do 
program search to find constructions for or optimize various combinatorial 
problems.

One of these problems was the Shannon capacity of cycle graphs on an odd number
of vertices. This file will talk only about the case of C7.

The best known lower bound comes from an independent set of size 367 in the
fifth strong power of C7 [Polak and Schrijver 2019]. FunSearch recovers this
result but through a different construction.

You may look at the github and the paper for more details and code.  
===

FunSearch's approach is to greedily add nodes to the independent set based on
some priority function. The LLMs sole job is to optimize this priority function.
Here is the function it came up with:

```py 
def priority(el: tuple[int, ...], num_nodes: int, n: int) -> float:
	"""Returns the priority with which we want to add `el` to the set.""" 
	score = 0
	for i in range(n): 
		if el[i] == el[(i + 2) % n]: 
			score += 1 
		else: score -= 1
		x = ((n - 2) * el[i] - el[(i + 1) % n]
			 - el[(i + 2) % n] - (n + 1) * el[(i + 3) % n]) % num_nodes
		score -= 0.5 * (x - el[(i + 1) % n]) ** 2 
		score += 0.1 * (num_nodes - 1 - (x - 1) % num_nodes) ** 2 
		score += 0.2 * (num_nodes - 1 - (x - 2) % num_nodes) ** 2 
	return score 
```

Parameters: el is the tuple representing the node, num_nodes is the number of
nodes in the underlying cycle graph, n is the power the graph is raised to, so
(num_nodes, n) = (7, 5).

The first thing to notice is that this function is fairly overfit. Here's its
results for other powers: 
2 = 8 
3 = 24 
4 = 73 
5 = 367 
6 = 741

From the Polak and Schrijver paper, we have the following results/bounds: 
2 =		10 
3 =		33 
4 \in	[108, 115] 
5 \in	[367, 401]

So the priority function is fairly overfit to the specific case of the fifth
power.  (No bounds for the 6th power are given in that paper, but we can see
that it's not a good independent set since 741^(1/6) < 3.0082, whereas 367^(1/5)
> 3.2578 [remember we only care about the kth root of the independent set in the
kth graph power].)

I also played around with the function for a bit, changing random things, and it
is clear that this is a local optimum.
===

Now we analyze and modify the function a little bit (for the specific case of
(C7)^5).

The easiest part of the function to "interpret" is the if/else block. A
reasonable interpretation is that it is favouring nodes with repeated elements,
to allow more freedom in other vertices.

However, one may ask the question of whether there is any significance to
checking elements a distance of 2 apart (el[i] == el[(i+2)%n]). There is none;
consider this:

Elements in (3, 1, 6, 0, 5) which are a distance of 2 apart, are the same as
elements in (3, 6, 5, 1, 0) that are 1 apart.

Likewise, we may rearrange the indices according to any cyclic permutation
generated by repeated addition (i.e., taking steps of 1, 2, 3, etc. are all the
same).

Thus we may change el[i] == el[(i+1)%n] without changing the size of the
independent set.

However, there are other parts of the function that rely on the specific
permutation of the indices so we must modify them as well. Every expression of
the form (i+k)%n in the code where i is an index and k is some offset should be
instead changed to (i + k*3)%n, since 3 is the multiplicative inverse of 2 mod
5, and we've scaled our "step size" down from 2 to 1.

(I did not explain that well, please try to consider it for yourself and it will
be clear).

This obviously doesn't functionally change the function, but it is a curiosity
that may aid in interpreting it.
===

A small piece of interpretation that I don't fully understand is that x clearly
has "units" of an element of Z_7, since it is computed using `% num_nodes`, and
later (x-1) and (x-2) are also modded by num_nodes.

I don't know why `x - el[(i+1)%n]` doesn't mod by num_nodes, but adding that
makes it worse.  

Also the line `num_nodes - 1 - (x-1)%num_nodes` and the corresponding line for
(x-2) are reversing the order of the cycle.
===

Finally, after some fiddling with the constants, we may actually remove the line
`score += 0.1 * (num_nodes - 1 - (x - 1) % num_nodes) ** 2` by changing the
constants in the other two `score (+-)=` lines.

Thus, the following priority function with our modifications gives the same
result of 367: 

```py 
def priority(el, num_nodes, n): 
	score = 0 
	for i in range(n): 
		if el[i] == el[(i+1)%n]: 
			score += 1 
		else: 
			score -= 1
		x = ((n-2) * el[i] - el[(i+3)%n] 
			- el[(i+1)%n] - (n+1) * el[(i+4)%n]) % num_nodes

		score -= 0.8 * (x - el[(i+3) % n]) ** 2 
		score += 0.3 * (num_nodes - 1 - (x-2) % num_nodes) ** 2

	return score 
``` 

Those constants 0.8 and 0.3 have some range to them.  
===

Final thoughts:
- The program overfits
- The program evades obvious interpretation or generalization
- We are able to remove a whole line simply by tweaking some constants
- An additional factor in the process, maybe a human, to make drastic changes
  might get the program out of local minima. I wonder if the if/else block is 
  vestigial as an early heuristic the LLM tried, and the program would do better
  without it.

Finally, the independent set my modified function found can be found at ./indset367.txt
===

Addendum (2024-07-25): I experimented with taking some large subset of the independent set found and then extending it with integer linear programming, still not set over 367