Implement true string addition
Python 3, 177 170 163 130 bytes



lambda a,b:s(d(a)^d(b))
def s(n,x=0,s=''):
 while n:n-=1;s+=chr(n%256);n&gt;&gt;=8
 return s
def d(n,c=0):
 while s(c)!=n:c+=1
 return c


Try it online!

-14 bytes thanks to notjagan

-33 bytes thanks to Leaky Nun (and switched endianness)

I have no business trying to golf anything in Python, but I didn't want to use Lua since this method needs large exact integers to work on reasonable length stings. (Note: the algorithm is still Really Slow when ramping up the string length.) This is mostly just to provide an answer ;)

Each string is self-inverse, and the empty string is the identity. This simply performs xor under a simple bijection between strings and non-negative integers. s is a helper function that computes the bijection (one way only), and d is the inverse.

Non-slow version (148 bytes, courtesy of Leaky Nun):

lambda a,b:s(d(a)^d(b))
def s(n,x=0,s=''):
 while n:n-=1;s=chr(n%256)+s;n&gt;&gt;=8
 return s
def d(n,c=0):
 while n:c=c*256+ord(n[0])+1;n=n[1:]
 return c


Try it online!

I'm going to hijack this for a group-theory primer as well.

Any right inverse is a left inverse: inv(a) + a = (inv(a) + a) + e = (inv(a) + a) + (inv(a) + inv(inv(a))) = inv(a) + (a + inv(a)) + inv(inv(a)) = (inv(a) + e) + inv(inv(a)) = inv(a) + inv(inv(a)) = e

This also means that a is an inverse of inv(a).

Any right identity is a left identity: e + a = (a + inv(a)) + a = a + (inv(a) + a) = a

The identity is unique, given other identity f: e = e + f = f

If a + x = a then x = e: x = e + x = (inv(a) + a) + x = inv(a) + (a + x) = inv(a) + a = e

Inverses are unique, if a + x = e then: x = e + x = (inv(a) + a) + x = inv(a) + (a + x) = inv(a) + e = inv(a)

Following the proofs should make it fairly easy to construct counterexamples for proposed solutions that don't satisfy these propositions.

Here's a more natural algorithm I implemented (but didn't golf) in Lua. Maybe it will give someone an idea.

function string_to_list(s)
  local list_val = {}
  local pow2 = 2 ^ (math.log(#s, 2) // 1) -- // 1 to round down
  local offset = 0
  list_val.p = pow2
  while pow2 &gt; 0 do
    list_val[pow2] = 0
    if pow2 &amp; #s ~= 0 then
      for k = 1, pow2 do
        list_val[pow2] = 256 * list_val[pow2] + s:byte(offset + k)
      end
      list_val[pow2] = list_val[pow2] + 1
      offset = offset + pow2
    end
    pow2 = pow2 // 2
  end
  return list_val
end

function list_to_string(list_val)
  local s = ""
  local pow2 = list_val.p
  while pow2 &gt; 0 do
    if list_val[pow2] then
      local x = list_val[pow2] % (256 ^ pow2 + 1)
      if x ~= 0 then
        x = x - 1
        local part = ""
        for k = 1, pow2 do
          part = string.char(x % 256) .. part
          x = x // 256
        end
        s = s .. part
      end
    end
    pow2 = pow2 // 2
  end
  return s
end

function list_add(list_val1, list_val2)
  local result = {}
  local pow2 = math.max(list_val1.p, list_val2.p)
  result.p = pow2
  while pow2 &gt; 0 do
    result[pow2] = (list_val1[pow2] or 0) + (list_val2[pow2] or 0)
    pow2 = pow2 // 2
  end
  return result
end

function string_add(s1, s2)
  return list_to_string(list_add(string_to_list(s1), string_to_list(s2)))
end


The idea is basically to split the string based on the power-of-two components of its length, and then treat these as fields with a missing component representing zero, and each non-missing component representing numbers from 1 up to 256^n, so 256^n+1 values total. Then these representations can be added component-wise modulo 256^n+1.

Note: This Lua implementation will have numeric overflow problems for strings of sizes greater than 7. But the set of strings of length 7 or less is closed under this addition.

Try it online!