Number Theory
The number-theoretic theorem of Abouabdillah is about antichains in the partially ordered set EN consisting of the positive integers in the interval, partially ordered by divisibility. With this partial order, an antichain is a set of integers within this interval, such that no member of this set is a divisor of any other member. It possible to prove using ideas related to Dilworth's theorem that the maximum number of elements in an antichain of E2n is exactly n: there exists an antichain of this size consisting of all the numbers in the subinterval, so the maximum size of an antichain is at least n. However, there are only n odd numbers within the interval, for each odd number c in this interval at most one number of the form 2kc may belong to any antichain, and every number in the interval has this form for some c, so the maximum size of an antichain is also at most n.
Abouabdillah's theorem characterizes more precisely the numbers that may belong to an antichain of maximum size in E2n. Specifically, if x is any integer in the interval, decompose x as the product of a power of two and an odd number: x = 2kc, where c is odd. Then, according to Abouabdillah's theorem, there exists an antichain of cardinality n in E2n that contains x if and only if 2n < 3k + 1c.
The smallest value in any maximum antichain of E2n is at least 2k, where 3k + 1 is the first power of three that is greater than 2n, as had been posed as a problem by Paul Erdős (1937) and solved by Emma Lehmer (1939). Lehmer's solution immediately implies the special case of Abouabdillah's theorem for c = 1. Abouabdillah's theorem generalizes this solution to all values within the given interval.
Read more about this topic: Abouabdillah's Theorem
Famous quotes containing the words number and/or theory:
“I will not adopt that ungenerous and impolitic custom so common with novel writers, of degrading by their contemptuous censure the very performances, to the number of which they are themselves adding—joining with their greatest enemies in bestowing the harshest epithets on such works, and scarcely ever permitting them to be read by their own heroine, who, if she accidentally take up a novel, is sure to turn over its insipid leaves with disgust.”
—Jane Austen (1775–1817)
“We commonly say that the rich man can speak the truth, can afford honesty, can afford independence of opinion and action;—and that is the theory of nobility. But it is the rich man in a true sense, that is to say, not the man of large income and large expenditure, but solely the man whose outlay is less than his income and is steadily kept so.”
—Ralph Waldo Emerson (1803–1882)