From: ikastan@uranus.uucp (Ilias Kastanas) Subject: Re: Binary operation in a field Date: 26 Nov 2000 05:39:32 GMT Newsgroups: sci.math Summary: [missing] In article <8vno96$6vh$1@nntp.stanford.edu>, Vaughan R. Pratt wrote: @In article , @Eric Katz wrote: @>If F is a field is it possible to express the multiplication in F @>X*Y (a binary operation) using the binary operation X-Y (subtract) @>and the unary operation 1/X (multiplicative inverse) ? @ @No. When X=Y=0, subtraction can only produce zero, so the first @reciprocal performed will be 1/0. @ @Vaughan Pratt Right; so let us also allow zero-testing. If X or Y passes, the answer is 0 (ehm, X-X). Otherwise we have available 1 (X/X), -a (0-a), a+b (a-(a-b)), and thus any integer. By polarization, squaring suffices ( xy = (x+y)^2 -(x-y)^2) /4 ). To get z^2, zero-test z, z-1; if they fail, z^2 = z + 1/(1/(z-1) - 1/z). Ilias ============================================================================== From: John Rickard Subject: Re: Binary operation in a field Date: 26 Nov 2000 21:37:03 +0000 (GMT) Newsgroups: sci.math David W. Cantrell wrote: : In article <8vq7mk$8v9r$1@hades.csu.net>, ikastan@uranus.uucp (Ilias : Kastanas) writes: : >By polarization, squaring suffices ( xy = ((x+y)^2 -(x-y)^2) /4 ). : Again, it seems that the binary operation of division (which we were : not given) is required here. Is there some way around this difficulty? Yes, assuming we're not in characteristic 2. Given 4xy, we get xy as xy = 1/(a+a+a+a), where a = 1/(4xy). -- John Rickard ============================================================================== From: ikastan@uranus.uucp (Ilias Kastanas) Subject: Re: Binary operation in a field Date: 29 Nov 2000 10:05:25 GMT Newsgroups: sci.math In article <900k9u$nq5$1@nntp.stanford.edu>, Vaughan R. Pratt wrote: @In article <8vt25t$e6u$1@agate.berkeley.edu>, @David Wagner wrote: @>Ilias Kastanas wrote: @>>@Eric Katz wrote: @>>@>If F is a field is it possible to express the multiplication in F @>>@>X*Y (a binary operation) using the binary operation X-Y (subtract) @>>@>and the unary operation 1/X (multiplicative inverse) ? @>> @>> [...] let us also allow zero-testing. If X or Y passes, @>>the answer is 0 (ehm, X-X). Otherwise we have available 1 (X/X), No we don't. We assume it's given. @>>-a (0-a), a+b (a-(a-b)), and thus any integer. By polarization, squaring !!! Mmm... what characteristic does _this_ hold in!? @>>suffices ( xy = (x+y)^2 -(x-y)^2) /4 ). To get z^2, zero-test z, z-1; @>>if they fail, z^2 = z + 1/(1/(z-1) - 1/z). @> @>This fails in characteristic two. Can that case be handled as well? @ @Yes, because everything following "Otherwise" can be replaced by @"Otherwise the answer is X". You don't need *any* operations! @(For that matter "(ehm, X-X)" can be replaced by (X), in any field.) @ @Vaughan Pratt I suppose David's question is about arbitrary fields of characteristic 2. As Vaughan points out, the case {0,1} is trivial; and we could set up a similar game for, say, the 4-element field: in {0,1,a,a+1} (a^2 +a+1=0) once past 0,1 we notice X*X = X+1, X*Y = 1. But we can't keep on going like this. There is no uniformity... and there are infinite fields too. So, what can we do in general? Note that, with the usual caveats, a^2 b = a+ 1/(1/a + 1/(a + 1/b)). Thus 1, X, Y yield X^2 Y, XY^2, as well as X^2, Y^2, and (XY)^2. But, interestingly, they do _not_ yield XY ! I proved that the operations + and 1/ applied to 1, X, Y (in char=2) generate X^k Y^m _iff_ k, m are not both odd (k, m in Z). I would imagine it's a known result (anybody??). In a _finite_ field, there is a recourse of sorts: square (XY)^2 repeatedly until it becomes (XY)^2 again (as it must); back up one step, and there is your XY ! Of course this is a far cry from having an "ex- pression" for XY... It would seem then the bottom line for char=2 is "No". "2" is an odd prime indeed! Ilias