7
$\begingroup$

Is there any binary operation that is commutative, associative, and distributive over multiplication?

I asked this question in my head a while ago, and I posted it in various forums. However, having not found an answer, it has once again sparked my interest. I'm not looking for any trivial functions, and any base set would work for me ($\Bbb{Z}$, $\Bbb{Q}$, or $\Bbb{R}$), so long as it contains the integers.

*EDIT* OK, the operation doesn't have to be commutative, but it does have to be both left and right distributive over multiplication. (Does both left and right distributivity imply commutativity?)

*EDIT 2* I'm looking for a binary function that maps two integers to another integer, or two positive integers to another positive integer. I only realized this after the first answer was posted, so I apologize.

$\endgroup$
  • $\begingroup$ Of course, $x \circ y := y$ is not commutative anyway, and $x \circ y := c$ is not distributive over multiplication unless $c = 0$ or $c = 1$. $\endgroup$ – Travis Willse Dec 7 '14 at 5:18
  • 1
    $\begingroup$ "Does both left and right distributivity imply commutativity?" No. Matrix multiplication has left and right distributivity but is not commutative. $\endgroup$ – Jon Dec 9 '14 at 5:41
5
+50
$\begingroup$

The nicest way to do this if we restrict our attention to positive integers is to take something similar to Zander's answer... but work with prime powers. It should be able to be extended to positive rationals, if you're careful.

It works like this: if you have two integers of the form $$ a = \prod_{i=1}^n p_i^{k_i} $$ and $$ b = \prod_{i=1}^n p_i^{m_i} $$ where $n$ is simply the index of the highest prime present in the pair of integers (that is, it's an arbitrary number for representing the primes in question), then we define our operation as $$ a\circ b = \prod_{i=1}^n p_i^{k_i\times m_i} $$ With this operation, we have commutativity (obvious). We have associativity: $$ (a\circ b)\circ c = a\circ (b\circ c) = \prod_{i=1}^n p_i^{k_i\times m_i\times l_i} $$ We have distributivity: $$ a\circ (b\times c) = \prod_{i=1}^n p_i^{k_i\times (m_i+l_i)} = \prod_{i=1}^n p_i^{k_i\times m_i}\times \prod_{i=1}^n p_i^{k_i\times l_i} $$ (and similarly for the right-distributivity).

Interestingly, this operation maps any pair of coprime integers to one, and more generally the result of this operation on any pair of integers will produce an integer having only prime factors present in both the original integers. Some specific examples...

$$ p^m \circ p^n = p^{mn}\\ 100\circ 750 = 62500\\ 224\circ 147 = 49 $$

$\endgroup$
  • $\begingroup$ Thanks! Looking back on this question, it seems fairly easy if you already know the answer ;). $\endgroup$ – Edward Jiang Dec 14 '14 at 19:51
  • $\begingroup$ Any chance you could write PARI code that computes this function? $\endgroup$ – Edward Jiang Dec 14 '14 at 21:53
  • $\begingroup$ Sadly, I haven't ever used PARI, so no. $\endgroup$ – Glen O Dec 15 '14 at 11:26
2
$\begingroup$

Let $ a\circ b = a^{\log b} $ then $$ a\circ b = a^{\log b} = \exp(\log a\log b) = b^{\log a} = b\circ a\\ (a\circ b)\circ c = (a^{\log b})^{\log c} = \exp(\log a\log b\log c) = a\circ (b\circ c) \\ a\circ (b\times c) = a^{\log b + \log c} = a\circ b \times a\circ c \\ (a\times b)\circ c = a^{\log c} \times b^{\log c} = a\circ c \times b\circ c $$

$\endgroup$
  • $\begingroup$ Thank you for your answer. Just one thing though: you can't take the logarithm of zero, or negative numbers if you exclude complex numbers from the set. Your function only gives half of what I'm looking for. $\endgroup$ – Edward Jiang Dec 10 '14 at 1:27
  • $\begingroup$ Cases of negatives and zeros can be dealt with, if you're careful; taking absolute values for $a$ and $b$ in the definition, and then having the sign decided by the signs of $a$ and $b$ would work. For zero, it's obvious that $a=0$ and $|b|>1$ just produces zero... so the easiest approach would be to make the result zero if either value is zero. $\endgroup$ – Glen O Dec 14 '14 at 16:28
2
$\begingroup$

You want a pairing $\phi: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$ which is distributive over multiplication, commutative, and associative.

Let me ignore signs for now (any such map can have the signs stripped out and map to nonnegative integers).

It's possible that $\phi$ is "zero at a prime $p$" by having $\phi(p,1) = 0$, which implies any expression involving a factor of $p$ is zero.

Other than this, and not yet considering associativity (i.e. only distributivity and commutativity), $\phi$ is determined by $\phi(p,q)$ for primes $p$ and $q$, and these are unconstrained (i.e. any value in $\mathbb{Z}$) except by $\phi(p,q) = \phi(q,p)$ if we want commutativity.

Associativity adds the condition $\phi(\phi(p,q),r) = \phi(p,\phi(q,r))$. This is quite restrictive compared to the above, but still there are many maps satisfying this.

For example, take $\phi(p,q) = 2$ for all $p$ and $q$. This works.

What does this give for $\phi$? Define $f(n)$ to be the sum of the exponents in the prime factorization of $n$.

Then $\phi(m,n) = 2^{f(n)f(m)}$. This satisfies all your conditions. (Let it be zero if $m$ or $n$ is zero, and ignore factors of $-1$.)

This of course has a variant for any other prime in place of $2$. It's also an amusingly similar idea to the partial example over the reals. (That example may be fixed by ignoring signs in the input and giving zero as the result if either input is zero.)

There are many others. For example, to get something just slightly more complicated, partition the primes into two sets, one containing $2$ and one containing $3$. Let $\phi(p,q)$ be $2$ if either is in the first set, and $3$ if they're both in the second. (There's also a variant: $2$ if both in the first, $3$ if both in the second, $0$ if one of each.)


We can also consider the map, instead of pairing, version:

$\phi: (\mathbb{Z},\cdot) \rightarrow \mathrm{End}(\mathbb{Z},\cdot)$

The condition $\phi(a)(b\cdot c) = \phi(a)(b) \cdot \phi(a)(c)$ is the statement that $\phi(a)$ is in $\mathrm{End}(\mathbb{Z},\cdot)$.

Then $\phi(a\cdot b)(c) = \phi(a)(c) \cdot \phi(b)(c)$ is the statement that $\phi$ is a morphism of monoids from $(\mathbb{Z},\cdot)$ to $\mathrm{End}(\mathbb{Z},\cdot)$. (Where given $f$ and $g$ we let $(f \cdot g)(c) = f(c) \cdot g(c)$. If $f$ and $g$ are endomorphisms of $(\mathbb{Z},\cdot)$, so is $f\cdot g$.)

The positive integers with multiplication are a free, unital monoid generated by the primes. (Signs and zero fit into this picture as well.)

This is only the distributivity part of the story, but it's a nice way to think about it.

$\endgroup$
0
$\begingroup$

$a\circ b=ab\pmod 2\ \forall a,b\in \mathbb{N}$

Commutativity

$a\circ b=ab\pmod 2=ba\pmod 2=b\circ a$

Associavity

$a\circ (b\circ c)=(a\cdot (bc\pmod 2))\pmod 2=((ab\pmod 2)\cdot c)\pmod2=(a\circ b)\circ c$

Distributivity

  1. $a\circ (b\circ c)=(a\cdot (bc\pmod 2))\pmod 2=((ab\pmod 2)\cdot (ac\pmod 2))\pmod 2=(a\circ b)\circ(a\circ c)$

  2. $(a\circ b)\circ c=((ab\pmod 2)\cdot c)\pmod2=((ac\pmod 2)\cdot (bc\pmod 2))\pmod 2=(a\circ c)\circ(b\circ c)$

$\endgroup$
  • $\begingroup$ Nice, but the question wasn't for it to distribute over itself, but to distribute over regular multiplication. (Which this might do, I haven't checked.) $\endgroup$ – Travis Bemrose Jan 19 '16 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.