In fact it's not too hard to prove that, with only basic treasure, it's impossible to get 4 provinces any faster than 10 turns. Suppose we're trying to buy our 4th province on turn 9.
Some assumptions are clear. Obviously you open Silver/Silver. In the 1st reshuffle, you have $11 total in your deck, but not the ability to buy a province (best possible hand is CCCSS), so might as well get a Silver and a Gold on turns 3 and 4.
Then, in the 2nd reshuffle, you have $16 exactly in your deck among 14 cards. However, $7 of that is in coppers, and it's not possible to buy a province when 4 coppers are in your hand, so only one province can be bought on turns 5 or 6. To buy your 4th province on turn 9, you need a province on one of those turns. The other turn can do no better than a Gold.
Finally, in the 3rd reshuffle, you have no more than $19 in your deck among 16 cards. Thus, there simply isn't enough money to buy a province on all of turns 7, 8, 9.
(The only way to avoid this problem would be to buy nothing on two turns so that turn 9 would come after the 4th reshuffle. But to do this, you'd need to give up two Silver buys at least, so during the 3rd reshuffle, you would only have $15 in deck, not enough to buy two provinces.)
