Transcript Proximity Inversion Functions on the Non

Proximity Inversion Functions
on the Non-Negative Integers
Presented By
Brendan Lucier
June 5, 2005
CMS Summer 2005 Meeting
Automatic Sequences and
Related Topics
To be seen
Introduction and Problem Statement
A Solution
Proving Correctness
Future Work
To be seen
Introduction and Problem Statement
A Solution
Proving Correctness
Future Work
Our Problem
 Consider a puzzle where we must place points labeled (0,
1, 2, …, n) on the real number line.
 The points must be placed so that, given distinct points
labeled (k) and (k+a), the distance between the points is
at least 1/a. Denote the position of point k by f(k).
 We want to know: what is the optimal (smallest) total
amount of space required to place all of the points?
Example: First Six Values
Non-negative real number line:
Example: First Six Values
0
f(0) = 1
 Place point 0 somewhere; let’s say f(0) = 1
Example: First Six Values
0
1
f(0) = 1
f(1) = 2
 Place point 0 somewhere; let’s say f(0) = 1
 Distance between point 0 and point 1 must be at least 1/1 = 1; take f(1) = 2
Example: First Six Values
2
f(2) = 1/2
0
1
f(0) = 1
f(1) = 2
 Place point 0 somewhere; let’s say f(0) = 1
 Distance between point 0 and point 1 must be at least 1/1 = 1; take f(1) = 2
 Point 2 must be 1 away from point 1 and 1/2 away from point 0. Try f(2) = 1/2
Example: First Six Values
2
f(2) = 1/2




0
f(0) = 1
3
f(3) = 3/2
1
f(1) = 2
Place point 0 somewhere; let’s say f(0) = 1
Distance between point 0 and point 1 must be at least 1/1 = 1; take f(1) = 2
Point 2 must be 1 away from point 1 and 1/2 away from point 0. Try f(2) = 1/2
Continue in this fashion, placing six points
Example: First Six Values
4
f(4) = 0




2
f(2) = 1/2
0
f(0) = 1
3
f(3) = 3/2
1
f(1) = 2
Place point 0 somewhere; let’s say f(0) = 1
Distance between point 0 and point 1 must be at least 1/1 = 1; take f(1) = 2
Point 2 must be 1 away from point 1 and 1/2 away from point 0. Try f(2) = 1/2
Continue in this fashion, placing six points
Example: First Six Values
4
f(4) = 0





2
f(2) = 1/2
0
f(0) = 1
3
f(3) = 3/2
1
f(1) = 2
5
f(5) = 7/3
Place point 0 somewhere; let’s say f(0) = 1
Distance between point 0 and point 1 must be at least 1/1 = 1; take f(1) = 2
Point 2 must be 1 away from point 1 and 1/2 away from point 0. Try f(2) = 1/2
Continue in this fashion, placing six points
We have achieved a maximum of 7/3. Is this optimal for six values?
Example: First Six Values
4
f(4) = 0






2
f(2) = 1/2
0
f(0) = 1
3
f(3) = 3/2
1
f(1) = 2
5
f(5) = 7/3
Place point 0 somewhere; let’s say f(0) = 1
Distance between point 0 and point 1 must be at least 1/1 = 1; take f(1) = 2
Point 2 must be 1 away from point 1 and 1/2 away from point 0. Try f(2) = 1/2
Continue in this fashion, placing six points
We have achieved a maximum of 7/3. Is this optimal for six values?
No, there is a better solution:
3
f(3) = 0
1
f(1) = 1/2
4
f(4) = 1
2
f(2) = 3/2
5
0
f(5) = 2 f(0) = 11/5
The Full Problem
Suppose now we wish to place an infinite
number of points
We wish to find a way to do so in a
bounded amount of space. What is the
smallest amount of space required?
Problem History
 Motivated by the Constraint Satisfaction Problem
Given a set V of variables and a set C of constraints, find an
assignment that satisfies all the constraints
 Binary Constraint Problem
each constraint affects two variables
 Metric Space Binary Constraint Problem
Generalization: variables take values from a metric space
Constraints are of the form “Variables p and q must be assigned
values that have distance at least cp,q from each other”
The Metric Space generalization is due to D. G. Fon-Der-Flaass,
“Real-valued Frequency Assignment,” 1998.
A Metric Space BCP
 Our problem is a particular instance of the MSBCP:
The variables are the natural numbers N = {0, 1, 2, …}.
The metric space is the set of non-negative real numbers R+.
 Each number n is assigned a value f(n).
 Our constraints are cp,q = 1/|p-q|.
 If a function f satisfies these constraints, we say that f is
a proximity inversion function.
 Our goal is to find such a function f that minimizes
supn(f(n)); that is, uses the least amount of space on
the real number line.
To be seen
Introduction and Problem Statement
A Solution
Proving Correctness
Future Work
Numeration Systems
 A Numeration System is a method of representing non-negative integers. It
corresponds to a sequence S = { s1, s2, … } of ascending positive integers.
 A value v can be expressed with respect to S as a string x = x1x2…xn over
the alphabet of natural numbers, where v =
Σsixi .
 Example: the decimal numeration system is S = { 1, 10, 100, … }
 The representation is unique when we require certain properties to hold.
 The most basic property is that xi < si+1/si for all i.
 There are more general properties as well, due to A. Fraenkel, “Systems of
Numeration,” 1985.
 When a string meets these properties, we say that it is a valid
representation for an integer with respect to S.
 We’ll skip the general results and simply claim the properties for our
particular numeration system.
Our Numeration System
 Let Fi denote the ith Fibonacci number. F0 = 0, F1 = 1, F2 = 1, etc.
 Take S = { F2i : i ≥ 1 } = { 1, 3, 8, 21, … }
 We express an integer n as a string x corresponding to digits of n
over basis S. That is, n = ΣxiF2i
 Example: if n = 38, then n = 1*21 + 2*8 + 0*3 + 2*1, so the
representation of n is the string 2021
 Note that for any k,
3F2k > 2F2k + F2k-1
= F2k + F2k+1
= F2(k+1)
 Thus xk < F2k / F2(k+1) < 3 for all k, so the set of valid
representations with respect to S is over the alphabet {0,1,2}
 It turns out that a string x in {0,1,2}* is a valid representation if
and only if it does not contain any subwords of the form 21*2
The Solution
 Given an integer n, suppose its representation in S is
x = x1x2…xk
 We define our function f by f(n) := Σ(xi/F2i)
 That is, we take our digits for representation over basis
{ F2i }, then apply them to the basis { 1/F2i }
Example: if n = 38 then x = 2021, so f(n) = 2/1 + 0/3 + 2/8 +
1/21 = 193/84 ≈ 2.2976
 The supremum for this particular f is 1 + Σ(1/F2i)
≈2.5353…
Example
 Our solution f() places the first ten values as follows
0
8
0 1/8
3
6
1/3
2/3
1
9
1 9/8
4
7
2
5
4/3
5/3
2
7/3
To be seen
Introduction and Problem Statement
A Solution
Proving Correctness
Future Work
Proving the Result
We need to prove that f is a proximity inversion
function; that is, |f(p) - f(q)| ≥ 1/|p-q| holds for
all natural numbers p and q
We shall consider what this means in terms of
the representations for p and q with respect to
our numeration system
In most cases, the required property for strings
will reduce to a problem that is easier and more
intuitive to solve
Relative Order
 Suppose we have two natural numbers, p and q, represented w.r.t.
S by strings x and y, padded with zeros to be the same length.
 Example: if p = 38, q = 12, then we can take x = 2021, y = 1120
 We can determine which of p or q is larger by scanning the digits of
x and y from right to left. Whenever the strings first differ, the string
with the larger digit corresponds to the larger number.
 Example: if x = 101, y = 211, then y corresponds to the larger value
because after the common suffix 1, y has the larger digit 1 > 0.
 A similar property holds for f(p) and f(q). If we scan the two
representations x and y from left to right we get the relative
ordering of f(p) and f(q). This is not obvious, and the proof depends
on our particular numeration system S.
 Example: if x = 2021, y = 1120, then since x1 = 2 > 1 = y1 we
conclude that f(38) > f(12).
Intermediate Values
 Consider two nonequal natural numbers p and q.
 An intermediate value for p and q is an integer t such that
 t lies between p and q, and
 f(t) lies between f(p) and f(q).
 Example: both 4 and 6 are intermediate values for 3 and 7.
0
8
0 1/8
3
6
1/3
2/3
1
9
1 9/8
4
7
2
5
4/3
5/3
2
7/3
Intermediate Values (cont.)
 Lemma: if our function f is not a valid proximity inversion function, then there is a
pair of integers (p’, q’) such that
 |f(p’) - f(q’)| > 1/|p’-q’|, and
 there is no intermediate value for p’ and q’
 Proof: Suppose f is not a proximity inversion function. That is, there exist distinct
natural numbers p and q such that |f(p) - f(q)| > 1/|p-q|.
 If p and q do not have an intermediate value, we are done. Otherwise, let t be an
intermediate value.
 Then |p-t| < |p-q| since t is between p and q, and |f(p) - f(t)| < |f(p) - f(q)| since
f(t) is between f(p) and f(q).
 We conclude that |f(p) - f(t)| > 1/|p-t|.
 If p and t have an intermediate value t’, then by the same argument
|f(p) - f(t’)| > 1/|p-t’|. We continue this process until we are left with two integers
with no intermediate value.
 This process must terminate, since there are only finitely many integers between p
and q.
Intermediate Values (cont.)
 To prove that f is a proximity inversion function, it now suffices to show
that our constraint holds for integers p and q that do not admit an
intermediate value.
 But we have an easy way to characterize precisely when an intermediate
value exists, using valid representations!
 Given two valid representations x and y, they will correspond to integers
with an intermediate value precisely if exists a representation z that is
lexicographically between x and y when read both forward and backward.
 Example: for x = 2021, y = 1120, we can take z = 1211. Then 1120 < 1211 <
2021 and 0211 < 1121 < 1202, so z is an intermediate value for x and y.
 Finding such an intermediate string z is easy, so a simple case analysis
eliminates almost all possible strings x and y.
Strings with no
Intermediate Values
 Example: suppose one of the strings ends in 00, say y.
Then x must be of the form wc21k and y must be of the
form wc’0k+1 where (c,c’) is either (0,1) or (1,2)
 This is one of only five cases in which x and y do not
have an intermediate string z
 This reduction makes the problem much more
manageable. we can prove directly that strings of these
forms correspond to integers that do not violate our
constraints
To be seen
Introduction and Problem Statement
A Solution
Proving Correctness
Future Work
Optimality of Solution
 We have not yet proved that the solution is optimal
 It turns out that our function f, limited to a finite set of
integers {0,…,n}, is not optimal for that subset
 It appears that the optimal solution fn for {0,…,F2n} is
related to f():
0
3
6
1
4
7
2
5
0
1/3
2/3
1
4/3
5/3
2
7/3
Optimality of Solution
 We have not yet proved that the solution is optimal
 It turns out that our function f, limited to a finite set of
integers {0,…,n}, is not optimal for that subset
 It appears that the optimal solution fn for {0,…,F2n} is
related to f():
Set fn(0) = f(F2n-1) + 1/F2n-1
3
6
1
4
7
2
5
0
1/3
2/3
1
4/3
5/3
2
7/3
38/15
Optimality of Solution
 We have not yet proved that the solution is optimal
 It turns out that our function f, limited to a finite set of
integers {0,…,n}, is not optimal for that subset
 It appears that the optimal solution fn for {0,…,F2n} is
related to f():
Set fn(0) = f(F2n-1) + 1/F2n-1
Shift all other values so that mink{fn(k)} = 0
3
6
0
1/3
1
4
7
2/3
1
4/3
2
5
0
5/3
2
38/15
 If this were true, this would imply that f is optimal, as
maxk{fn(k)} converges to supn{f(n)}
Extending to Other Problems
 The method outlined here is only a solution to a
particular instance of a constraint satisfaction problem.
 Our approach was to take a function f and express it as
A numeration system S
A (simpler) function f* to perform on the basis elements of S
 We would like to generalize the results of this approach,
so it can be used to solve different constraint problems.
 In particular, can all metric space BSPs be solved this
way? If not, what are the necessary and sufficient
conditions on the distance constraints for such a solution
to exist?
Questions?