C0 - C0 = [-1, 1]

Febraruary 12, 2011
Stuart Anderson

We want to solve A = B - C with A in [0, 1] and B, C in the Cantor set. As in Proof #1, A, B, and C are written as ternary strings, with B and C free of the digit 1. Let's think of the problem as A + C = B, set up in the format of the usual grade-school arithmetic exercise with sums and carries at each digit location.

Now the basic limitation of Proof #1 is that the carry value propagates from right to left, so that one must have a starting point for the calculation at the right end of the digit sequence. Hence only finite digit sequences can be constructed, and topological arguments are needed to obtain the solution for the rest.

This can be avoided by the following trick borrowed from computer science: in designing an algorithm for a recursive calculation one tries to reformulate the problem to make as much of it as possible non-recursive, leaving only a minimal core of recursion. Let us then try to split the calculation into a recursive step which computes ONLY THE CARRY, and a non-recursive step which then specifies the solution.

At each digit location, one of the following 6 possibilities holds, where

  • i = the carry into this digit,
  • o = the carry out to the left neighbor digit, and
  • x is a free choice of 0 or 2:
     o i |    0 0    1 1    1 0    0 1    0 0    1 1
     a |    0    0    1    1    2    2
     + c |    x    2    2    0    0    x
     --- |    ---    ---    ---    ---    ---    ---
     = b |    x    0    0    2    2    x

When a = 0 or 2, i = o, and when a = 1, i = ˜o (the binary complement of o), and both of these relations are symmetrical in i and o. It is therefore clear that the carry can be propagated from left to right instead of right to left. Simply start with I(0) = 0 (so that the resulting number B will not exceed 1), and move to the right through the digits of A, toggling i(n) whenever a(n) = 1. This constructs a unique (binary) carry string I for any A in [0, 1].

With the carry string available, the computation of each digit of B and C is independent and can be carried out non-recursively. Specifically, let D = A + I mod 3 (where the addition and mod 3 reduction is separate for each digit). Then define C by c(n) = 2·(d(n) == 1) and B by b(n) = 2·(d(n) == 2). (In other words, c(n) = 2 if d(n) is 1 and 0, otherwise; and similarly for b(n).) B and C are then the desired elements of the Cantor set.

B and C are also the SMALLEST pair that works, since we have chosen zero for every value of x. If we further define E by e(n) = x·(d(n) == 0), where each x is 0 or 2 arbitrarily, then B' = B + E and C' = C + E is another pair of solutions. Since I, B, and C are completely determined by A, the only variation possible is in E; hence the set of all B', C' is the complete set of solutions to the problem.

Further, the arbitrary choices in E can be described by choosing a binary string X in [0, 1] and letting 2·x(n) be the nth digit choice made in E (not the nth digit of E, but the nth occurrence of d = 0). Then each X corresponds to a solution B', C' and the full set of solutions is indexed by [0, 1] if there are infinitely many 0 digits in D. If D has only finitely many 0 digits, then of course there are finitely many choices. From this, we have the interesting corollary:

For every A in [0, 1], the number of distinct pairs of Cantor set members satisfying A = B - C is 2z, where z is the number of occurances of the digit 0 in D. This is true even if z is infinite, since 2card(N) = card([0, 1]).


[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Did you know?| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]