[lokedhs]

Can someone explain this sentence to me?

(In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧?)

  f(a, b) produces at most a or b, whichever is greater:
    f(a, b) ≤ max(a, b)

As far as I can tell, the result can never be greater than the smaller of a and b. I can't come up with a counterexample. Is there one?

[bnegreve]

> In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧?

'∧' usually denotes the logical AND operator, which does not operate on integer values, (i.e. writing 22 ∧ 78 = 6 is weird). So it's not a bad idea to give this function a different name.

He could have made that explicit though.

[eximius]

I think you're right. By definition it can't have any more 1's that the lesser has and it might have less 1's than the lesser has.

[Gankro]

You're correct, it can be changed to `min(a, b)`. A rough proof:

* assume WLOG `a = min(a, b)`

* `a & b` takes the set bits of `a` and produces a subset of them

* the value of an integer is `SUM 2^j` where the j-th bit is set

* removing positive elements from a sum can only make it smaller

* therefore & can only produce a value smaller than `a` (the minimum)

[escape_goat]

There is not, and there cannot be. However, even if he was figuring this all out from scratch, he could not have come up with the hand-written charts without realizing that.

I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance.

However, I cannot present to you the crucial difference between the maximum of two numbers and the minimum of two numbers that explains what he was thinking. This must exist for my hypothesized explanation to make sense.

[thaumasiotes]

> I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance.

It's worse than that; he mentions the identity function only to make a gross error about it. The identity function on (a, a) is (a, a), not a.

[coinomega]

I don't think you need to be so unforgiving?

If you want extra precision, a -> f(a, a) is Id.

Knowing that helped me understand one property of the chart, never said that was the most stunning of properties, and the best articulated one :-)

[jonsen]

The law x AND 1 = x is called the identity law.

The law x AND x = x is called the idempotence law.

Nothing to do with the identity function.

[thaumasiotes]

> If you want extra precision, a -> f(a, a) is Id.

What does this mean?

[coinomega]

The function which to any integer a associates f(a, a) with f defined as in the article is the identity function on the natural integer set.

[thaumasiotes]

Granted. g(a) = f(a,a) is indeed the identity function for all f such that f(a,a) = a. That seems pretty pointless as an observation. We have f, so we're observing that some other, unrelated function is the identity function?

[Strilanc]

A counterexample is 0 & -1 == 0.

[thedufer]

The given function is clearly only defined over naturals. In the first part using bits, there's no indication of how to encode negatives, and in the second part with the sum equation, f(-1,-1) >= 0 (and thus not equal to -1) for any reasonable definition of the modulo function paired with any `b`, which breaks one of the stated identities. In fact, that's true if you replace mod with _any_ function.

[Strilanc]

> The given function is clearly only defined over naturals.

The post doesn't specify. Programming languages do define it over the negatives, however. I just didn't want anyone going into python and asserting that a & b >= min(a,b).

> there's no indication of how to encode negatives

Just do the standard thing: use 2s complement arithmetic [1]. More concretely: set b to infinity and take the limit under the 2-adic metric [2]. For example, -2 & -1 has partial sums 0, 10, 110, 1110, 11110, etc. It's limiting to ...1111110, which is the 2's complement representation of -2.

1: https://en.wikipedia.org/wiki/Two%27s_complement

2: https://en.wikipedia.org/wiki/P-adic_number

[thedufer]

The laws given in the post were explicitly derived from the equation. Please explain how you used that to determine f(0, -1)?

[Strilanc]

Pick any `b` you want, even infinity, and evaluate:

    sum_n^b 2^n (floor(0/2^n) mod 2) (floor(-1/2^n) mod 2)

    sum_n^b 2^n * 0 * 1

    sum_n^b 0

    0

[thedufer]

Excellent. I'm glad we agree. You'll notice that the stated identity f(x,x) = x fails to hold over x < 0. I hope this is sufficient to make it clear that the equation does not consider the negatives?

[TTPrograms]

I'm not quite sure they have enough paper for numbers with infinite boolean expansions.

[nthacker]

Yeah for an AND function, f(a,b) <= min(a,b)