Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log_b a}$:

$$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n} $$

In human language, what does non-polynomial difference mean? Why was $n/\log n$ compared to $n^{\log_ba}$ in the first place?

In addition, what happens if I replaced $n/\log n$ with $n/\log^n$, where $\log^n$ is the log-star function. Would a similar type of analysis take place?

A non-polynomial difference just means that the quotient $\frac{n/\log n}{n^{\log_b a}} = \frac{1}{\log n}$ is not a polynomial, where here $a=b=2$. To see why this is a problem, let's try to apply the master theorem.

Case 2 states that if $f(n) = O(n^{\log_b a} \log^k n)$ for some $k \geq 0$ then $T(n) = O(n^{\log_b a} \log^{k+1} n)$. In our case we can choose $k = 0$ and obtain the bound $T(n) = O(n\log n)$. If we also had $f(n) = \Omega(n^{\log_b a} \log^k n)$ then $T(n) = \Omega(n^{\log_b a} \log^{k+1} n)$, but this doesn't hold in our case.

Case 1 states that if $f(n) = O(n^c)$ for $c \log_b a$ then $T(n) = \Omega(n^c)$. In our case $c < 1$ so this case also doesn't apply.

Summarizing, the master theorem only gives the upper bound $T(n) = O(n\log n)$. We trivially have $T(n) = \Omega(n/\log n)$, but this doesn't match the upper bound.

We can determine the exact asymptotics using the Akra–Bazzi method. In our case $p = 1$ and $g(x) = x/\log x$, so $T(n) = \Theta(n(1+G(n))$ where
$$ G(x) = \int_1^x \frac{g(u)}{u^2} \, du = \int_1^x \frac{du}{u\log u} = \log\log x. $$
(Formally, we have to change the lower bound of the integration from $1$ to $e$.) We conclude that $T(n) = \Theta(n\log\log n)$.

StackExchange Computer Science Q#32419, answer score: 3