avoiding-collinearity

Code and tests for determining an upper bound on the number of collinear points on an infinite walk on a finite set of vectors in Z^3.

This project is split into two parts. One is a Maven Java project with the bulk of the functionality. The other is a Cargo Rust project with a single, smaller program.

To build the Java project, install Maven from https://maven.apache.org/ and run mvn package from within the maven directory.

To build the Rust project, install Cargo from https://www.rust-lang.org/tools/install and run cargo build from within the cargo directory.

Java project commands

Once the jar file has been built by mvn package a jar file will have been created at maven/target/avoidingcollinearity-1.1.0.jar.

Running java -jar avoidingcollinearity-1.1.0.jar will startup a command line interface with a number of commands available. These commands are described below here with some examples.

Print the first 220 symbols of the sequence of the infinite word generated by the morphism:

PrintSymbolSequence 220 --one-indexed

Get the index of the last new subword of a given length using:

IndexOfLastNewSubword 9

Draw a sequence of trapezoids using:

DrawTrapezoids wholeAndRt3 343 /home/finn/trapezoids.png

Assert a bound on the ratio of largest and smallest distances between trapezoids separated by a minimum and maximum number of indices using:

AssertBoundedDistanceRatio 7 48 wholeAndRt3 9 0

Find the largest count of trapezoids separated by at most a given number of indices that are intersected by a single straight line using:

CountCollinearTrapezoids 7 wholeAndRt3

Get a disjoint set of intervals that contain all subwords of a given length for the symbol sequence:

DistinctSubwordIntervals 343

More usage information for each the com.commands can be found by using the --help option, for example:

PrintSymbolSequence --help

Rust project

The cargo/count-collinear subdirectory contains a Rust program for counting the largest number of collinear points in the first N points of a particular sequence of points. The collinearity_data.csv file contains the result of checking for the largest number of collinear points in the first 10 million terms of the sequence. This used approximately 2.7 years of CPU time spread between AWS Fargate spot instances, my personal laptop, and a PC belonging to my brother, Robin Lidbetter.

The computation showed that there are no 7 collinear points in the first 10 million terms of the sequence.

The computation can be reproduced by running

cargo run --release

and entering

10000000.

Other configurations are available for running this in parallel by splitting it up into many jobs, enqueuing an encoding of those jobs in AWS SQS and reading and processing those jobs, optionally writing the results to AWS DynamoDb.

To prove the weaker claim that there are no 7 collinear points in any 7^5=16807 consecutive terms of the sequence, the command

cargo run --release --bin collinearity16807

can be used. This command takes approximately 95 minutes to run to completion on a 2020 M1 Macbook Air.