January 12 Information

What does it mean for a theorem to be sharp? The context is:

Theorem: If ${\displaystyle {\mathcal {F}}=\left\{\left(A_{i},B_{i}\right)\right\}_{i=1}^{h}}$ is a ${\displaystyle \left(k,l\right)}$-system, then ${\displaystyle h\leq {\binom {k+l}{k}}}$.
The Theorem is sharp, as shown by the family ${\displaystyle {\mathcal {F}}=\left\{\left(A,X\backslash A\right):A\subset X,\left\vert A\right\vert =k\right\}}$, where ${\displaystyle X=\left\{1,2,\dots ,k+l\right\}}$.

-- 130.195.253.145 ( talk) 00:30, 12 January 2015 (UTC) reply

I found two other instances of the word "sharp" in the preceding pages of the book and they're used in a more clear sense ("... these arguments supply a rather sharp estimate...", "...the upper bound is sharp..."), but I'm not sure if it's the same sense as is being used here. But they make me think that maybe it means that the upper bound is obtained exactly. -- 130.195.253.145 ( talk) 00:35, 12 January 2015 (UTC) reply

This is described in List of mathematical jargon#Descriptive informalities. A sharp bound is one that cannot be made any more constrained without some cases failing. -- Mark viking ( talk) 00:42, 12 January 2015 (UTC) reply

Firstly the problem ...

For a given rational function ${\displaystyle f(x)={\frac {x}{d}}}$ where ${\displaystyle x<d}$ express the function as a series of terms ${\displaystyle {\frac {x_{1}}{d_{1}}}...{\frac {x_{n}}{d_{n}}}}$ such that:

1. ${\displaystyle x>x_{1}..x_{n}}$ and ${\displaystyle d_{n-1}<d_{n}}$
2. ${\displaystyle x_{n-1}\geq {x_{n}}\geq 1}$
3. ${\displaystyle 1\leq {x_{n}}<{d_{n}}}$
4. ${\displaystyle n\geq {1}}$
5. ${\displaystyle x\geq {1}}$
6. ${\displaystyle d\geq {3}}$

For the first few examples this is trival..

${\displaystyle {\frac {2}{4}}={\frac {1}{2}}}$

${\displaystyle {\frac {3}{4}}={\frac {1}{2}}+{\frac {1}{4}}}$

${\displaystyle {\frac {2}{5}}={\frac {1}{3}}+{\frac {1}{15}}}$

${\displaystyle {\frac {3}{5}}={\frac {1}{2}}+{\frac {1}{5}}}$

${\displaystyle {\frac {4}{5}}={\frac {3}{4}}+{\frac {1}{20}}}$

Is there a general pattern that I could use for x/6 x/7 etc...? ShakespeareFan00 ( talk) 16:45, 12 January 2015 (UTC) reply

If this is a question better suited to Wikiversity LMK. ShakespeareFan00 ( talk) 16:53, 12 January 2015 (UTC) reply

No, we should be able to help. You could start by picking your first fraction to add, so that it's less than the target fraction. So, if your target is 4/7, you could start with 1/2. Then just do the math of subtracting that from the target, using a common denominator:

${\displaystyle {\frac {4}{7}}-{\frac {1}{2}}={\frac {8}{14}}-{\frac {7}{14}}={\frac {1}{14}}}$

Then put it into the desired form:

${\displaystyle {\frac {4}{7}}={\frac {1}{2}}+{\frac {1}{14}}}$

StuRat ( talk) 17:44, 12 January 2015 (UTC) reply

Egyptian fraction is (sort of) a special case of this problem, where all the ${\displaystyle {x_{n}}}$ are equal to 1, but without the restriction that ${\displaystyle d\geq {3}}$. AndrewWTaylor ( talk) 20:13, 12 January 2015 (UTC) reply

I was only applying ${\displaystyle d\geq {3}}$ because the cases where relatively trival.. I presume there is a way of converting ${\displaystyle {\frac {1}{d}}}$ (i.e unit fracrions) into approximations based on an Egyptian Fraction, presumably by doubling and proceeding as for ${\displaystyle {\frac {2}{x}}.}$

(and the article linked gives a good explanation.).

Thanks for the linked article.

A different problem is how to compute an approximate fraction based the condition that ${\displaystyle {\frac {x_{n}}{d_{n}}}={\frac {1}{2^{n}}}}$, but that's essentially binary division.

At this point I wonder if computers use series for doing floating point division in simple cases. For obviously huge divisions you use logs right? ShakespeareFan00 ( talk) 21:10, 12 January 2015 (UTC) reply

Log is a more difficult operation than division, so it wouldn't be used. Check out Division algorithm for some methods. It appears that SRT division is used in Intel processors. -- Meni Rosenfeld ( talk) 21:34, 12 January 2015 (UTC) reply