attachment:notes_kotsireas.txt of msri07/notes

   1 2:00 p.m.
   2 Combinatorial Designs
   3 Ilias Kotsireas
   4 
   5 Combinatorial Design Theory:
   6 	Is it possibel to arrang eelemnts of a finite set into subsets so that certain properties are satisfied.
   7 	Applicatoins to cryptography, optical communications, wireless communciations, coding theory
   8 
   9 Weighing Matrices:
  10 	A weighing matrix W = W(n,k) of weight k is a square nxn matrix with entries -1,0,1, having k non-zero entries per row and column, with inner product of distinct rows zero.
  11 	W . Transpose(W) = kI_n   where I_n is the nxn identity matrix.
  12 
  13 What can we do?
  14 Plan of attack:  Establish pattenrs for the locations of the 5 zeros in solutions for weighing matricies of the type W(2n,2n-5)
  15 This would take us down from 3^(2n) to 2^(2n-5) operations.
  16 
  17 Idea:  Analyze the wolution sets for W(2n,2n-5) for all odd n up to 15
  18 Since we want the weighing matrix to be constructed from two circulants, when we fix 4 zeroes, the location of the 5th zero is fixed in a very symmetric position.  A proof of this would probably imply that there is an infinite class of a certain type of polynomials.
  19 
  20 To help, since certain problems still require too many operations, is to calculate certain autocorrelating functions.  NPAF and PAF, (non)Periodic Autocorrelating Functions.
  21 
  22 NPAF = 0 implies PAF = 0.  And these functions are related in other ways as well.
  23 Weighing matricies come from sequences with zero PAF.
  24 
  25 Power Spectral Density theorem (PSD):  Two sequences can be used to make up ciculant matrices A and B that will give W(2n,k) weighing matrices if and only if a certain relation in the terms of the discrete fourier transform (DFT) hold.
  26 
  27 There is a theorem that provides a horizontal relationship between the sequence and the PSD, which allows for faster calculating of the DFT coefficients we need.
  28 
  29 A solution to W(2*29,53) can now be found (using the PSD and a string sorting algorithm) within a day with serial programs.  However, a solution for W(2*33,61) is still not found.  It could be that the algorithm is failing because one of the PSD values is an integer.
  30 
  31 It turns out, that there ARE cases where the PSD value can be an integer.
  32 
  33 An error bounding algorithm was created to find when the algorithm may fail.