Perfect ruler

A perfect ruler of length [math]\displaystyle{ \ell }[/math] is a ruler with integer markings [math]\displaystyle{ a_1=0 \lt a_2 \lt \dots \lt a_n=\ell }[/math], for which there exists an integer [math]\displaystyle{ m }[/math] such that any positive integer [math]\displaystyle{ k\leq m }[/math] is uniquely expressed as the difference [math]\displaystyle{ k=a_i-a_j }[/math] for some [math]\displaystyle{ i,j }[/math]. This is referred to as an [math]\displaystyle{ m }[/math]-perfect ruler. An optimal perfect ruler is one of the smallest length for fixed values of [math]\displaystyle{ m }[/math] and [math]\displaystyle{ n }[/math].

Example

A 4-perfect ruler of length [math]\displaystyle{ 7 }[/math] is given by [math]\displaystyle{ (a_1,a_2,a_3,a_4)=(0,1,3,7) }[/math]. To verify this, we need to show that every positive integer [math]\displaystyle{ k\leq 4 }[/math] is uniquely expressed as the difference of two markings:

[math]\displaystyle{ 1=1-0 }[/math]

[math]\displaystyle{ 2=3-1 }[/math]

[math]\displaystyle{ 3=3-0 }[/math]

[math]\displaystyle{ 4=7-3 }[/math]

See also

• Golomb ruler
• Sparse ruler
• All-interval tetrachord