home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / research / 436 < prev    next >
Encoding:
Text File  |  1992-09-01  |  3.0 KB  |  74 lines
  1. Newsgroups: sci.math.research
  2. Path: sparky!uunet!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!usenet
  3. From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
  4. Subject: Re: mixed-field arithmetic problems
  5. References: <MOON.92Sep1110158@moon.ee.usu.edu>
  6. Nntp-Posting-Host: dn66.dse.beckman.com
  7. Message-ID: <a_rubin.715377118@dn66>
  8. Sender: Daniel Grayson <dan@math.uiuc.edu>
  9. X-Submissions-To: sci-math-research@uiuc.edu
  10. Organization: University of Illinois at Urbana
  11. X-Administrivia-To: sci-math-research-request@uiuc.edu
  12. Approved: Daniel Grayson <dan@math.uiuc.edu>
  13. Date: Tue, 1 Sep 1992 19:51:58 GMT
  14. Lines: 58
  15.  
  16. In <MOON.92Sep1110158@moon.ee.usu.edu> moon@moon.ee.usu.edu (Todd Moon) writes:
  17.  
  18.  
  19. >Here is a problem in mixed field arithmetic.  In what follows, + will
  20. >denote addition over the field of reals, and | will denote addition
  21. >over GF(2).  Multiplication is over the reals.
  22.  
  23. >consider a system of equations such as
  24.  
  25. >a_1 c_0               + a_2 c_3               = s_0
  26. >a_1 c_1               + a_2 c_4               = s_1
  27. >a_1 c_2               + a_2 c_5               = s_2
  28. >a_1 (c_0 | c_1)       + a_2 (c_3 | c_5)       = s_3
  29. >a_1 (c_1 | c_2)       + a_2 (c_3 | c_4 | c_5) = s_4
  30. >a_1 (c_0 | c_1 | c_2) + a_2 (c_3 | c_5)       = s_5
  31. >a_1 (c_0 | c_2)       + a_2 (c_4 | c_5)       = s_6
  32.  
  33. >where a_1 and a_2 are real and known, the s_i are real and known, and
  34. >the unknowns c_i are in GF(2) (that is, either 0 or 1).  Although the
  35. >problem has been written similar to a set of linear equations, it is
  36. >easy to verify that this is not a linear set of equations.
  37.  
  38. >1) Find the set of c_i that satisfy this set of equations.  For this
  39. >problem, it can be accomplished simply by combinatorial search
  40. >techniques.  However, there are larger problems of interest similar to
  41. >for which searching is impractical.
  42.  
  43. For equations of the form:
  44.  
  45. (E_i) a_1 f_i(C) + a_2 g_i(C) = s_i, we have:
  46.  
  47. If (1)  all of a_1, a_2, a_1+a_2, and a_1-a_2 are nonzero, then E_i
  48. translates to f_i(C) = t_i_1 and g_i(C) = t_i_2.
  49.  
  50. If (2) a_2 = 0 , then E_i translates to f_i(C) = t_i
  51.  
  52. If (3) a_2 = a_1, then E_i translate to f_i(C) = 0 and g_i(C) = 0; or
  53. f_i(C) | g_i(C) = 1; or f_i(C) = 1 and g_i(C) = 1
  54.  
  55. If (4) a_2 = -a_1, then E_i translates to f_i(C) = 0 and g_i(C) = 1; or
  56. f_i(C) | g_i(C) = 0; or f_i(C) = 1 and g_i(C) = 0
  57.  
  58. If (5) a_1 = a_2 == 0 , then the equations do not depend upon the c's.
  59.  
  60. In any of these cases, the (E_i) reduce to a linear set of equations over
  61. GF(2), which can be solved by the usual methods.
  62.  
  63. (This method fails if we have a_1, a_2, and a_3, and they are all equal. 
  64. It works, for example, if the a_i's are "almost sum-distinct"; for any s
  65. there are at most two sum(a_i c_i) equal to s.)
  66.  
  67.  
  68. --
  69. Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  70. 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  71. My opinions are my own, and do not represent those of my employer.
  72. My interaction with our news system is unstable; if you want to be sure I see a post, mail it.
  73.  
  74.