Projective set experiments

From stacky wiki

Question: how many points in $\mathbb P_{\mathbb F_2}^n$ are needed to touch all lines? It can be done with $2^n-1$ points (take the hyperplane at infinity), and requires at least $\frac 13(2^{n+1}-1)$ points (dividing total number of lines by number of lines through a point).

import random

def setup( dim ):
    points = [[0],[1]]
    i = dim
    while i>0:
        points = [x+[0] for x in points] + [x+[1] for x in points]
        i-=1
    points = [tuple(x) for x in points]
    points.remove(tuple([0]*(dim+1)))
    lines = set([tuple(sorted([a,b,tuple([a[i]^b[i] for i in range(len(a))])])) for a in points for b in points if b!=a])
    return (points, lines)

def search( dim ):
    points, lines = setup(dim)
    size = 2**dim - 1
    found = False
    print "looking for size",size
    while True:
        S = random.sample(points,size)
        found = True
        for L in lines:
            if len([p for p in L if p in S])==0: # S misses L
                found = False
                break
        if found:
            print size, S
            size-=1

def build( dim ):
    S=[]
    points, lines = setup(dim)
    for L in lines:
        if len([p for p in L if p in S])==0: # S misses L
            S.append(random.choice(L))
    return len(S), S