TITLE: Frankl's conjecture and Oeis sequence A188163
QUESTION [7 upvotes]: For every natural number $c \geq 2$, let $f(c)$ denote the least natural number $f$ with the following property : every union-closed family of sets with at least $f$ members has $c$ members whose intersection is nonempty. If I'm not wrong, it is easy to prove that $f(c)$ always exists. Frankl's conjecture amounts to say that $f(c) \leq 2c-1$.
If $c-1$ is a power of $2$, then $f(c) \geq 2c-1$ (look at the family of all subsets of a set with cardinality $k$, where $c-1 = 2^{k-1}$). Thus, if $c-1$ is a power of $2$, then Frankl's conjecture (if true) is optimal.
But if $c-1$ is not a power of $2$, it can happen that $f(c) < 2c-1$, so that Frankl's conjecture is not optimal in these cases.
For example, if I'm not wrong, $f(4) = 6$ and $f(6) = 10$. So, I searched the Oeis site for a sequence $A$ with the following properties :
$A(1+2^{k-1}) = 1+2^{k}$;  $A(4) = 6$; $A(6) = 10$.
A188163 ( http://oeis.org/search?q=3%2C5%2C6%2C9%2C10&language=english&go=Search) :
1, 3, 5, 6, 9, 10, 11, 13, 17, 18, 19, 20, 22, 23, 25, 28, 33, 34, 35, 36, 37, 39, 40, 41, 43, 44, 46, 49, 50, 52, 55, 59, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 77, 78, 79, 81, 82, 84, 87, 88, 89, 91, 92, 94, 97, 98, 100, 103, 107, 108, 110, 113, 117, 122
seems a good candidate, since (numbering $A(n)$from $A(1) = 1$)
$A(3) = 5$, $A(5) = 9$, $A(9) = 17$ and so on, thus $A(1+2^{k-1}) = 1+2^{k}$ in the limits of the table (I don't know if this is always true, I discover this sequence today)
and also  $A(4) = 6$; $A(6) = 10$.
(For $c = 1$, we have $f(c) = 2 \neq A(c) = 1$, but it doesn't seem very important to me.)
Is there literature about a possible relation between $f(c)$ and $A188163(c)$ ?

REPLY [7 votes]: Let me elaborate a bit on what I said over at Polymath11.
There is a nice survey on Frankl's conjecture, where the following similar question is discussed in Section 8. Let $\phi:\mathbb{N}\to\mathbb{N}$ be the function where $\phi(n)$ is the smallest maximal abundance of an element of the ground-set of a union-closed family with $n$ members. Frankl's conjecture asserts that $\phi(n)\geq \tfrac{n}{2}$, and computing $\phi(n)$ for small $n$ suggests that $\phi$ may coincide with A004001. The survey notes that this sequence always provides an upper bound for $\phi$, but this upper bound is not always tight and there remains a gap. This has been shown by Renaud.
Concerning your $f$, note that it is by definition the Galois adjoint of $\phi$,
$$f(c)\leq n \quad\Leftrightarrow\quad c\leq\phi(n),$$
meaning that $f(c)$ equals the smallest $n$ for which $c\leq \phi(n)$ holds. Since $\phi$ is monotone and surjective, this implies that $f(c)$ is the smallest $n$ for which $\phi(n) = c$ holds; this reflects exactly the relation between A188163 and A004001. Therefore your question is equivalent to asking about the relation between $\phi$ and A004001, which has been answered by Renaud as above.


TITLE: $\operatorname{ord}(a^k)$ is a divisor of $\operatorname{ord}(a)$
QUESTION [1 upvotes]: I'm trying to prove this for a finite group $G$.
Along with the book's hint, I have the following proof:
Let $\operatorname{ord}(a)=n$. Then
$$(a^k)^n=a^{kn}=a^{nk}=(a^n)^k=e.$$
It follows that $kn$ is a multiple of $n$, so $kn=nb$ for an integer $b$. So, $k=b$.
But I'm not sure what $k=b$ gives me.

REPLY [1 votes]: Andrew's comment is good; a next step is to use the division algorithm and suppose toward a contradiction that ord$(a) = n = q $ ord$(a^k) + r$ (since you know ord$(a^k) \le $ord(a)).


TITLE: Summing over trivial zeros of Riemann zeta function in explicit formulas
QUESTION [0 upvotes]: Formulas for prime-counting functions
$$\tag{1.a}\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac {1}{2}}\ln(1-x^{-2})$$
$$\tag{2.a}\Pi _{0}(x)=\operatorname {li} (x)-\sum _{\rho }\operatorname {li} (x^{\rho })-\ln 2+\int _{x}^{\infty }{\frac {dt}{t(t^{2}-1)\ln t}}$$
$$\tag{3.a}\pi _{0}(x)=\operatorname {R} (x)-\sum _{\rho }\operatorname {R} (x^{\rho })-{\frac {1}{\ln x}}+{\frac {1}{\pi }}\arctan {\frac {\pi }{\ln x}}$$
Thus corresponding sums over trivial zeros are:
$$\tag{1.b}-\sum _{n=1}^{\infty}\frac{x^{-2 n}}{-2 n}=-{\frac {1}{2}}\ln(1-x^{-2})$$
$$\tag{2.b}-\sum _{n=1}^{\infty}\operatorname {li} (x^{-2 n})=\int _{x}^{\infty }{\frac {dt}{t(t^{2}-1)\ln t}}$$
$$\tag{3.b}-\sum _{n=1}^{\infty}\operatorname {R} (x^{-2 n})=-{\frac {1}{\ln x}}+{\frac {1}{\pi }}\arctan {\frac {\pi }{\ln x}}$$
I can verify $(1.b)$ by series expansion of $\log (x+1)=\sum _{n=1}^{\infty } \frac{(-1)^{n+1} x^n}{n}$ around x=0 and then substituting $x\to-x^{-2}$.
How do we verify or derive $(2.b)$ and $(3.b)?$
Another related question:
I can compute residue at s=0 in $(1.a)$ which is equal $-\ln 2\pi$ by using Taylor expansion.
But how can we compute residues at s=0 which appear in $(2.a)$ as  $-\ln 2$ and in $(3.a)$ as $0$?

REPLY [0 votes]: So here is my attempt on $(2.b)$ (which I do not consider very obvious):
$$-\sum _{n=1}^{\infty}{\operatorname {li} (x^{-2 n})}=-\sum_{n=1}^{\infty}{\int _{0}^{x^{-2 n}}{\frac {1}{\ln t}\,dt}}$$
Using substitution $t=u^{-2 n}$ so that $dt=-2 n\,u^{-2 n-1} du$:
$$=-\sum_{n=1}^{\infty}{\int _{\infty}^{x}{\frac {-2 n\,u^{-2 n-1}}{\ln(u^{-2 n})}\,du}}=-\sum_{n=1}^{\infty}{\int _{\infty}^{x}{\frac {-2 n\,u^{-2 n-1}}{-2 n \ln u}\,du}}=-\sum_{n=1}^{\infty}{\int _{x}^{\infty}{\frac {-u^{-2 n-1}}{\ln u}\,du}}$$
$$=\sum_{n=1}^{\infty}{\int _{x}^{\infty}{\frac {u^{-2 n}}{u \ln u}\,du}}=\int _{x}^{\infty}{\frac {\sum_{n=1}^{\infty}{u^{-2 n}}}{u \ln u}\,du}=\int _{x}^{\infty}{\frac {1/(u^2-1)}{u \ln u}\,du}=\int _{x}^{\infty}{\frac {1}{u (u^2-1) \ln u}\,du}$$
So $(3.b)$ still remains open, so feel free to comment or answer on this one.
...and also the "residue question" still open.


TITLE: Minimum perimeter of a three-sided rectangular fence with given enclosed area
QUESTION [0 upvotes]: A three-sided fence is to be built next to a straight section of a river, which forms the fourth side of a rectangular region. The enclosed area is equal to 1800 ft^2. Find the minimum perimeter and the dimensions of the corresponding enclosure.
What I have so far:
Area = length * width = 1800, Perimeter = 2 * length + 2 * width
Substituting gives Perimeter = 3600/width + 2 * width.
The derivative is then -(3600)/(width^2) + 2 = 0. But this ultimately results into width^2 = -1800 and that's not possible??

REPLY [0 votes]: All these answers are correct, but they all set the derivative of some function to zero, an understandable reflex when one is asked to find the minimum of some variable subject to constraints.  However, a simpler route is available.  Using the variables in the accepted answer of @N. F. Taussig, $$\begin{align*}
P(l) & = l + 2\left(\frac{1800~\text{ft.}^2}{l}\right)\\
     & = l + \frac{3600~\text{ft.}^2}{l}
\end{align*}$$Replacing $P(l)$ with simply $P$, multiplying through by $l$, and re-arranging.we obtain$$l^2-Pl+3600 =0$$Applying the Quadratic Formula, we obtain:$$l = \frac{P\pm\sqrt{P^2-4\times 3600}}{2}$$For a real solution, the discriminant must be non-negative.  $P=\sqrt{4 \times 3600}=120$ is the smallest possible value of P that keeps the discriminant non-negative...


TITLE: How many ways I can place some, possibly all, five distinct balls into three distinguishable bins?
QUESTION [2 upvotes]: I want to know how many ways I can place some, possibly all of five balls each a distinct color into three distinguishable bins. Each bin must have at least one ball and I do not need to use all of the balls.
The numbers are small so I consider the cases:
(x,y,z) is the number of items in each bin. With only 5 items to use (at most) I have these possibilities:
(1,1,1) (5*4*3)/(1!1!1!)
(2,1,1) (5*4*3*2)/(2!1!1!)
(1,2,1) (5*4*3*2)/(2!1!1!)
(1,1,2) (5*4*3*2*1)/(2!1!1!)
(2,2,1) (5*4*3*2*1)/(2!2!1!)
(1,2,2) (5*4*3*2*1)/(2!2!1!)
(2,1,2) (5*4*3*2*1)/(2!2!1!)
(3,1,1) (5*4*3*2*1)/(3!1!1!)
(1,3,1) (5*4*3*2*1)/(3!1!1!)
(1,1,3) (5*4*3*2*1)/(3!1!1!)
Then take the total of the right column. I first count the ways of putting the balls in as if order mattered, then divide by the number of arrangements possible of balls that are grouped together in each of the three bins to account for repeats.
That's not a bad process for small numbers, but is there any way to streamline this to solve the problem?:
How many ways I can place some, possibly all of n balls each a distinct color in to m distinguishable bins? Each bin must have at least one ball and I do not need to use all of the balls.

REPLY [2 votes]: Say that you have $n$ balls and $m$ bins, obviously with $n\ge m$. If you did not have the requirement that each bin receive at least one ball, there would be $(m+1)^n$ possible outcomes: for each of $n$ balls you choose a specific bin or set it aside, for a total of $m+1$ choices. Now we need only count the ‘bad’ distributions, i.e., those that leave at least one bin empty.
The same reasoning that we just used shows that there are $m^n$ distributions that leave bin $1$ (say) empty; since there are $m$ bins, this comes to a total of $m(m^n)=m^{n+1}$ distributions that leave at least one bin empty. Unfortunately, we’ve counted any distribution that omits two bins twice, so we have to compensate by adding $(m-1)^n$ ‘doubly bad’ distributions for each of the $\binom{m}2$ pairs of bins.
In short, this is an inclusion-exclusion problem, and the final result is
$$\begin{align*}(m+1)^n-\binom{m}1m^n+\binom{m}2(m-1)^n-\dots&=\sum_{k=0}^m(-1)^k\binom{m}k(m+1-k)^n\\
&=\sum_{k=0}^m(-1)^{m-k}\binom{m}k(k+1)^n\;.
\end{align*}$$