a new strategy for computing c_n

This is a follow-up to this post, were attempts to find a line-free set in ${}[3]^5$ with at least 150 elements failed, and where we’ve agreed that programming the search would be better.

Thinking about this I’ve come up with the following strategy (let’s work with ${}[3]^5$ but the same can de done with ${}[3]^n$), I haven’t tested it yet I’m just spelling it out:

2) then at each lattice site (i.e word $w\in {}[3]^5$) attach two things: the list of lines it belongs to, and the total number of such lines (a kind of weight, let’s call it $\ell (w)$)

for example for the lattice site 11111 we have all the following lines:
with one wildcard 1111*, 111*1, 11*11, 1*111, *1111; with two wildcards 111**, 11*1*, 1*11*, *111*, 11**1, 1*1*1, *11*1, 1**11, *1*11, **111; and so on…

3) then order the lattice sites according to their weight $\ell (w)$ from high to low, and remove sites starting from those with highest weight, until the remaining set is line-free.

That is, my idea here is akin to Fourier analysis: do the big features first (here: high intersections, a kind of backbone) then do the fine details (the lines with few intersections, the flesh). Of course for this to work we have to hope that there are “enough” sites with high to moderate weight, so that we can remove as few sites as possible, and that the procedure is “monotone” otherwise all kinds of local minima issues may arise.

I’m going to try out the idea on ${}[3]^4$ first to see if we do recover what we already know, and then move on to ${}[3]^5$.

Note in particular that if this idea is correct: the 11..111 site should always be removed since it has the heighest weight, but also that to find the biggest line-free sets for a given $n$ one should not re-use the line free sets at $n-1$ but instead recompute the weights and do the search accordingly.

I’ll be offline a few hours and back this afternoon with some code hopefully.

Tags:

4 Responses to “a new strategy for computing c_n”

1. Jason Dyer Says:

Just note we’ve already used the greedy strategy you describe

http://thetangentspace.com/wiki/Hales-Jewett_Theorem

although we haven’t tried randomizing it yet.

2. Thomas Sauvaget Says:

Oh alright, I’ll have a close look, thanks.

3. Jason Dyer Says:

Any progress on the code?

4. Thomas Sauvaget Says:

Yes Jason, I now have a new algorithm which I’ve tried by hand on $[3]^2$, $[3]^3$ and $[3]^4$ and it did produce all the expected largest line-free sets. I don’t know if it works beyond that though, it may well need further adjustements to make it truly universal.

I’ve been actively coding it in the last few days, but I’m not quite there yet, and unfortunately I have some very important things workwise which means I really must put it on hold until mid-march.

I will then resume working on it and post the carefully checked program with any new results on the $c_n$.