Testwiki:Reference desk/Archives/Mathematics/2015 January 12

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < January 11 ! width="25%" align="center"|<< Dec | January | Feb >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 12

Sharpness of a theorem

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

Theorem: If

$ℱ={\left\{(A_i,B_i)\right\}}_{i=1}^h$

is a

$(k,l)$

-system, then

$h\le (\genfrac{}{}{0ex}{}{k+l}{k})$

.
The Theorem is sharp, as shown by the family

$ℱ=\{(A,X\mathrm{\setminus }A):A\subset X,\left|A\right|=k\}$

, where

$X=\{1,2,\dots ,k+l\}$

.

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

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)

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)

Fractions

Firstly the problem ...

For a given rational function $f(x)=\frac{x}{d}$ where $x<d$ express the function as a series of terms $\frac{x_1}{d_1}...\frac{x_n}{d_n}$ such that:

1. $x>x_1..x_n$ and $d_{n-1}<d_n$
2. $x_{n-1}\ge x_n\ge 1$
3. $1\le x_n<d_n$
4. $n\ge 1$
5. $x\ge 1$
6. $d\ge 3$

For the first few examples this is trival..

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

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

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

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

$\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)

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

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:

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

Then put it into the desired form:

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

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

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

I was only applying $d\ge 3$ because the cases where relatively trival.. I presume there is a way of converting $\frac{1}{d}$ (i.e unit fracrions) into approximations based on an Egyptian Fraction, presumably by doubling and proceeding as for $\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 $\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)

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)