Sorting using ring operations
This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible.

I think you're going to have to specify more precisely which operations you can perform on the RAM, because to compute it needs to be able to do more than just arithmetic. Memory indexing? Comparisons? If you allow bitwise binary operations (including shifts) and either hashing or unbounded memory then it's all over, even without multiplication or division:

def sort(intlist):
    backtrans = {}
    bits = 0
    for x in intlist:
        y = 1&lt;&lt;x
        if y in backtrans:
            backtrans[y][1] += 1
        else:
            backtrans[y] = [x,1]
        bits |= y
    while bits:
        y = bits &amp;~ (bits - 1)
        x,reps = backtrans[y]
        for i in range(reps):
            yield x
        bits &amp;=~ y


There's also a linear time sorting algorithm (for large enough machine words) by Albers and Hagerup 1997 but I'm not sure which operations it needs or whether it could be adapted to use only arithmetic and not bit manipulation. The reference is:

Albers, Susanne; Hagerup, Torben (1997), "Improved parallel integer sorting without concurrent writing", Information and Computation 136 (1): 25–51.