#!/usr/bin/python -i ######################################################################## # # Giant steps, depth, and bridge numbers # # by Sangbum Cho and Darryl McCullough # # Version of May 3, 2009 # # Contact: dmccullough@math.ou.edu # # This is a Python 2.3 script that implements algorithms from the papers # # "Constructing knots tunnels using giant steps" and # "Tunnel leveling, depth, and bridge numbers." # ######################################################################## # # All the major functions accept either binary or step sequence inputs. # # You can convert between the binary invariants string and the # step sequence of a principal path using these utilities: # # Depth> steps2binary( 'DRRRDRDLLLDLDRR' ) # '0011100011100' # # Depth> binary2steps( '0011100011100' ) # 'DRRRDRDLLLDLDRR' # # Depth> binary2steps( '0011100011100' ).lower() # 'drrrdrdllldldrr # # Like all functions accepting step sequences, binary2steps accepts # lower-case inputs. # ######################################################################## # # The function gst analyzes the constructions of a tunnel using # giant steps. # # For example, using the example from "The depth of a knot tunnel", # # Depth> gst( '0011100011100' ) # 4 # # If you want more details of the calculation, use # # Depth> gst( '0011100011100', verbose = True ) # # The block configurations are R1, L2, L1, R2, and # # M_5 * ... * M_2 = [ [ 2, 2 ], [ 2, 2 ] ]. # # This tunnel has 4 minimal giant step constructions # # Depth> gst( '00111000111001', verbose = True ) # # The block configurations are R1, L2, L1, R2, and # # M_5 * ... * M_2 = [ [ 2, 2 ], [ 2, 2 ] ]. # # The final block is a nabla. # # This tunnel has 8 minimal giant step constructions. # ######################################################################## # # The function fibonacci calculate the fibonacci number F_\tau( a, b ). # For our standard example, we find # # Depth> fibonacci( '0011100011100', 2, 2, verbose=True ) # # F_\tau( 2, 2 ) = 182. # # The iteration sequence is: # # 2, 2, 4, 6, 10, 14, 18, 22, 40, 62, 102, 142, 182 # # The iteration sequence tells the intermediate values. # # Depth> fibonacci( '0011100011100', 4, 5, verbose=True ) # # F_\tau( 4, 5 ) = 414. # # The iteration sequence is: # # 4, 5, 9, 14, 23, 32, 41, 50, 91, 141, 232, 323, 414 # # The function lowerBound calls fibonacci with the minimum # possible starting values 2 and 2, and upperBound calls it # with the maximum possible starting values, based on the number # of depth 1 cablings in the cabling sequence. # # Depth> lowerBound( '0011100011100' ) # The minimum bridge number is 182. # # Depth> upperBound( '0011100011100', verbose = True ) # # The maximum bridge number is 414. # # The iteration sequence is: # # 4, 5, 9, 14, 23, 32, 41, 50, 91, 141, 232, 323, 414 # # # fibonacci warns of impossible inputs. For example: # # Depth> fibonacci( '0011100011100', 3, 5, verbose=True ) # # Warning: The starting bridge numbers should satisfy # 2 <= c2 <= c3 <= c3 + 1. # # F_\tau( 3, 5 ) = 373. # # The iteration sequence is: # # 3, 5, 8, 13, 21, 29, 37, 45, 82, 127, 209, 291, 373 # # # To suppress warnings, set warnings = False: # # Depth> fibonacci( '0011100011100', 3, 5, verbose=True, warnings = False ) # # F_\tau( 3, 5 ) = 373 # # The iteration sequence is: # # 3, 5, 8, 13, 21, 29, 37, 45, 82, 127, 209, 291, 373 # # # Finally, the function bridgeSet gives the set of possible # bridge numbers for the given principal path. It is not yet known # that these all occur, but it appears extremely likely that they do. # # Depth> bridgeSet( '0011100011100' ) # # [182, 232, 273, 323, 364, 414] # ######################################################################## import re, sys sys.ps1 = 'Depth> ' sys.ps2 = ' ... ' class Matrix: def __init__( self, a=0, b=0, c=0, d=0 ): self.a, self.b, self.c, self.d = a, b, c, d def __str__(self): return "[ [ %d, %d ], [ %d, %d ] ]" % (self.a, self.b, self.c, self.d) def __mul__(self,n): # defines self * n return Matrix( self.a * n.a + self.b * n.c, self.a * n.b + self.b * n.d, self.c * n.a + self.d * n.c, self.c * n.b + self.d * n.d ) # regular expressions binary = re.compile( '(0|1)*' ) startingSteps = re.compile( 'DR' ) legalSteps = re.compile( 'LL|LD|DR|DL|RD|RR' ) def isBinary( s ): """Check whether a string consists of 0's and 1's.""" if binary.match( s ).end() == len( s ): return True return False def isSteps( s ): """Check whether a string consists of L's, D's, and R's and is a legal step sequence. Accepts small-letter strings.""" s = s.upper() if startingSteps.match( s ) == None: return False for k in range(1,len(s)-1): if legalSteps.match( s[k:k+2] ) == None: return False return True def binary2steps( inputString ): """Convert binary strings to step sequences.""" if not isBinary( inputString ): print 'Error: illegal binary invariants string.' return reverseMode = { 'L' : 'R', 'R' : 'L' } returnString = 'DR' for s in inputString: if s == '0': if returnString[-1] == 'L': returnString += 'L' elif returnString[-1] == 'D': returnString += reverseMode[ returnString[-2] ] elif returnString[-1] == 'R': returnString += 'R' elif s == '1': if returnString[-1] == 'D': returnString += returnString[-2] else: returnString += 'D' return returnString def steps2binary( inputString ): """Convert step sequences to binary strings.""" if not isSteps( inputString ): print 'Error: illegal step sequence.' return returnString = '' previousStep = 'R' secondPreviousStep = 'D' for step in inputString[2:]: if step == previousStep: returnString += '0' elif step == 'D': returnString += '1' elif step == secondPreviousStep: returnString += '1' else: returnString += '0' secondPreviousStep = previousStep previousStep = step return returnString def numDepthOneCablings( inputString ): """Find the number of semisimple cablings of a principal path. Assumes that the tunnel is not semisimple, so returns 2 for empty string input.""" if isSteps( inputString ): binary = steps2binary( inputString ) elif isBinary( inputString ): binary = inputString else: print 'Error: illegal input string.' return None initialZeros = re.compile( '^0+' ) initialZeroMatch = initialZeros.match( binary ) if initialZeroMatch: return initialZeroMatch.end() + 2 else: return 2 def depth( inputString ): if isBinary( inputString ): steps = binary2steps( inputString ) elif isSteps( inputString ): steps = inputString.upper() else: print 'Error: illegal input string.' return None return len( [ x for x in steps if x == 'D' ] ) def findConfiguration( aBlock ): """An auxiliary function for gst .""" if aBlock[1] == 'L': if len( aBlock ) == 2: return 'L1' else: return 'L2' if aBlock[1] == 'R': if len( aBlock ) == 2: return 'R1' else: return 'R2' def gst( inputString, verbose=False ): if isBinary( inputString ): steps = binary2steps( inputString ) elif isSteps( inputString ): steps = inputString.upper() else: print 'Error: illegal input string.' return None # Make dictionary to look up matrices according to block type. configurationMatrix = { 'R1' : Matrix(1, 1, 0, 1), 'L1' : Matrix(1, 0, 1, 1), 'R2' : Matrix(0, 1, 0, 1), 'L2' : Matrix(1, 0, 1, 0) } corridorBlocks = re.compile( 'DR+|DL+|D\$' ) blocks = corridorBlocks.findall( steps ) # Check for depth 1 case. if len( blocks ) == 1: print '\nThe tunnel has depth 1, so has a unique', \ 'minimal giant step construction.\n' return matrixList = [] configurations = [] # always ignore the first block blocks = blocks[1:] # ignore the final block for now for aBlock in blocks[:-1]: conf = findConfiguration( aBlock ) configurations.append ( conf ) matrixList.append( configurationMatrix[ conf ] ) if len( blocks[-1] ) > 1: # the tunnel does not form a nabla with \nabla( n ) conf = findConfiguration( blocks[-1] ) configurations.append ( conf ) matrixList.append( configurationMatrix[ conf ] ) matrixList.reverse() m = reduce( (lambda x, y: x * y), matrixList, Matrix(1, 0, 0, 1) ) matrixList.reverse() if verbose == True and configurations != []: matrixPrintout = '\n '.join( map( str, matrixList ) ) if len( configurations ) == 1: print '\nThe block configuration is %s, and\n' % configurations[0] print ' M_2 = %s.' % matrixPrintout else: print '\nThe block configurations are %s, and\n' % \ ', '.join( configurations ) print ' M_%s * ... * M_2 = %s.' % ( 1+len(matrixList), str( m ) ) # calculate the number of paths if len( blocks[-1] ) == 1: # bottom triangle of corridor is a nabla num = m.a + m.b + m.c + m.d if verbose == True: print '\nThe final block is a nabla.' else: if conf == 'L1' or conf == 'L2': num = m.a + m.b else: num = m.c + m.d if verbose == True: if num is 1: print '\nThis tunnel has 1 minimal giant step construction.\n' else: print '\nThis tunnel has %d minimal giant step constructions.\n' % num else: return num def fibonacci( inputString, c2=2 , c3=2, verbose = False, warnings = True, \ lb = False, ub = False ): if isSteps( inputString ): binary = steps2binary( inputString ) elif isBinary( inputString ): binary = inputString else: print 'Error: illegal input string.' return None numDepthOnes = numDepthOneCablings( binary ) if lb == True: c2, c3 = 2, 2 elif ub == True: c2, c3 = numDepthOnes, numDepthOnes + 1 # If warnings are in force, check for impossible inputs. if warnings == True: if c2 < 2 or 1 < c3 - c2 or c2 > c3: print '\nWarning: The starting bridge numbers should satisfy', \ '\n 2 <= c2 <= c3 <= c3 + 1.' elif c2 > numDepthOnes or c3 > numDepthOnes + 1: print """\nWarning: The given starting bridge numbers are impossible. The cabling sequence contains %d depth 1 tunnels, so they should satisfy c2 <= %d and c3 <= %d.""" % \ (numDepthOnes, numDepthOnes, numDepthOnes + 1) # Handle the semisimple case. input = binary.lstrip('0') if input == '': # The tunnel is semisimple. print 'This tunnel has depth 1. Its bridge number satisfies', \ '2 <= b <= %d.' % numDepthOneCablings + 2 return # The tunnel is regular. # Iteratively find the previous, pivot, and current minimum bridge numbers pivotBridgeNum = c2 previousBridgeNum = c2 currentBridgeNum = c3 minList = [c2, c3] for step in input: if step == '0': previousBridgeNum = currentBridgeNum elif step == '1': pivotBridgeNum = previousBridgeNum previousBridgeNum = currentBridgeNum currentBridgeNum += pivotBridgeNum minList.append( currentBridgeNum ) if verbose == True: if lb == True: print '\nThe lower bound for br(K_\\tau) is %d.' % currentBridgeNum elif ub == True: print '\nThe upper bound for br(K_\\tau) is %d.' % currentBridgeNum else: print '\nF_\\tau( %d, %d ) = %d.' % ( c2, c3, currentBridgeNum ) print '\nThe iteration sequence is:' print '\n %s\n' % ', '.join( map( str, minList) ) else: return currentBridgeNum def lowerBound( s ): fibonacci( s, verbose = True, lb = True ) def upperBound( s ): m = numDepthOneCablings( s ) fibonacci( s, verbose = True, ub = True ) def bridgeSet( inputString ): if isSteps( inputString ): binary = steps2binary( inputString ) elif isBinary( inputString ): binary = inputString else: print 'Error: illegal input string.' return None bridgeNumbers = [] numDepthOnes = numDepthOneCablings( binary ) for k in range(2, numDepthOnes + 1): bridgeNumbers.append( fibonacci( binary, k, k, verbose = False ) ) bridgeNumbers.append( fibonacci( binary, k, k + 1, verbose = False ) ) return bridgeNumbers